[백준][JAVA] 1260 : DFS와 BFS

내가 풀기는 커녕 기를 쓰고 풀다가 자꾸 타임아웃에 걸려 결국 남의 코드를 봤다

역시나 재귀를 사용하지 않았던 것이 문제였던 것 같다.

남의 코드를 봐도 이해가 안됐지만 예제 입력에 있는 가장 간단한 예시를 넣어보면서 이해했다.

다른 사람이 짠 코드가 재귀를 사용하는데 이해가 안된다면 무조건 손으로 따라 가보는 것을 추천한다.

 

<main>

import java.io.*;
import java.util.*;
public class Main{
    static int[][] adjacent; 
    static boolean[] checked; 
    static int n,m,start; 

    public static void main(String[] args) throws IOException {
        Scanner s = new Scanner(System.in);
        n = s.nextInt(); 
        m = s.nextInt(); 
        start = s.nextInt(); 

        adjacent = new int[1001][1001]; 
        checked = new boolean[1001]; 

        for(int i = 0; i < m; i++) {
            int x = s.nextInt();
            int y = s.nextInt();
            adjacent[x][y] = adjacent[y][x] = 1;
        }
        
        dfs(start);
        checked = new boolean[1001]; //dfs에서 checked 사용했으므로 초기화
        System.out.println();
        bfs();
    }

- 서로 인접한 정점의 정보를 인접 행렬 또는 인접 리스트에 저장한다.

+)인접 행렬과 인접 리스트에 대해 잘 정리해두신 블로그 :   https://sarah950716.tistory.com/12

 

- (1,1)을 입력 받는 경우 배열의 [1][1]에 그대로 저장하기 위해 배열의 크기는 N이 아닌 N+1로 설정해준다.

   ex) 정수를 최대 100개 입력할 수 있는 경우 배열의[101][101]이 사실상 100,100이므로 int[101][101]로 선언

 

- 행렬이나 리스트를 검사할 때 한 번 확인한 자리를 중복 확인하지 않기 위하여 해당 자리를 체크 해놓아야 한다.

  이를 위해 보통 boolean 형의 빈 배열을 만들고 검사 완료 시 검사한 위치를 true 로 초기화 시켜준다.

  +) 배열이름은 보통 checked 또는 visited를 많이 사용한다.

 

- 시작점을 입력받아 dfs를 호출하고 bfs는 매개변수 없이 호출한다.

 

여기까지가 main 을 간단히 설명한 것이지만 스스로 코드를 뜯어보지 않는다면

한 시간을 설명 해도 이해는 안될 것이라 생각한다.

 

<DFS>

     public static void dfs(int i) { //인접 행렬 사용
        checked[i] = true; 
        System.out.print(i + " "); 
        for(int j = 1; j <= n; j++) {
            if(adjacent[i][j] == 1 && checked[j] == false)
                dfs(j);
        }
    }

인접 행렬을 사용한 DFS 구현이다.

그래프 구현에 겁을 먹고 있던 나로써는 DFS 코드가 이렇게 짧다는 점에서 우선 어느정도 벽이 허물어졌다.

비록 다음 벽이 재귀였지만..

 

1. DFS에 시작점을 넣으므로써 한 번 방문한 것이 되기 때문에 checked 배열의 시작점 칸을 true로 초기화한다.

2. 방문한 정점을 터미널에 출력한다.

3. if(adjacent[i][j] == 1 && checked[j] == false)

 - 인접 행렬의 칸이 1이고 아직 방문하지 않은 칸을 만나면 해당 칸에 대해 DFS를 호출한다.

   ->여기서 앞으로 재귀가 반복적으로 발생한다.

 

<BFS>

 public static void bfs() { //인접 리스트 사용
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(start);
        checked[start] = true;
        System.out.print(start + " ");
        
        while (!queue.isEmpty()) {
            int temp = queue.poll(); 
            
            for (int j = 1; j <= n; j++) {
                if (adjacent[temp][j] == 1 && checked[j] == false) {
                    queue.offer(j);
                    checked[j] = true;
                    System.out.print(j + " ");
                }
            }
        }
    }
}

인접 리스트를 이용한 BFS 구현이다.

- 큐의 front에 추가 하는 함수 : offer

- 큐의 rear에서 삭제하는 함수 : poll

 

1. 연결 리스트를 이용한 큐를 선언한다.

 - start가 전역 변수로 선언 되었기 때문에 큐에 start부터 push 한다.

  * 일반적인 push 함수인 add,  remove가 아닌 offer와 poll을 사용하는 이유

       - add,  remove 사용 시 push 실패하는 경우 : 오류 발생

       - offer,  poll 사용 시 push 실패하는 경우 : false를 return

 

2. DFS 함수와 동일하게 checked 배열의 시작점 칸을 true로 초기화하고 방문한 정점을 터미널에 출력한다.

 

3. While문을 통해 Queue가 빌 때까지 반복한다.

 - (1) 큐의 front에 있는 데이터를 temp에 저장하고 큐에서 삭제한다.

 - (2) if(adjacent[i][j] == 1 && checked[j] == false)

            인접 행렬의 칸이 1이고 아직 방문하지 않은 칸을 만나면 큐에 추가한다.

 - (3) true로 초기화 후 터미널 출력