BFS

백준 2644번을 BFS를 이용해 Java로 풀어보았다.
처음에 문제에 대한 이해가 부족해서 이상한 조건을 스스로 만들어서 좀 돌아갔지만 알고보면 간단한 BFS 문제다.

---

한 다리씩 건너가며 탐색하기

BFS의 의미 그대로 너비 우선 탐색을 하며 내가 찾는 상대방 번호와 일치하는지 따져보면 된다.
큐의 사이즈만큼 반복문을 돌리며 조건에 맞는 녀석들을 추가해주고 큐가 빌 때까지 while문으로 돌리며 촌수를 높여주면 된다.

큐의 사이즈만큼 반복문을 돌리도록 한 이유는, 부모 방향으로 가든 자식 방향으로 가든 딱 한 다리 건너가는 것은 동일하기 때문에 한 텀에 추가되는 놈들은 모두 다 동일한 촌수를 갖기 때문이다.

중간에 내가 찾는 상대를 만나면 바로 return을 때리기 때문에 만약 상대를 찾지 못하고 while문을 벗어나게 되면 -1을 반환하도록 했다.

아래는 내가 작성한 bfs(int 사람1, int 사람2) 코드다.

static Integer bfs(int p1, int p2){
        int result = 0;
        Queue<Integer> q = new LinkedList<>();
        q.add(p1);

        while(!q.isEmpty()){
            int size = q.size();
            for(int i=0; i<size; i++){
                int cur = q.poll();
                visited[cur] = true;
                if(cur==p2) return result;
                for (int child = 1; child <= n; child++) {
                    if (map[cur][child] == 1) {
                        if (!visited[child])
                            q.add(child);
                    }
                }
            }
            result++; // 촌수 늘려주기
        }
        return -1;
    }

---

부모 자식 가릴 것 없이 연결된 관계면 표시해주기

처음에 착각한 것은 map[][]에 map[parent][[child]에만 연결 표시를 해주었다. 그랬더니 부모 쪽으로 올라가는 움직임과 자식 쪽으로 내려가는 움직임 사이에 차이가 생겨서 방향대로 따라 처리해줘야 하는 문제가 생겼다. 물론 따로 처리해줘도 결국엔 틀리게 나왔다.

중요한 것은 서로 연결돼있기만 하면 map[][]에 꼭 표시를 양쪽으로 다 해줘야 위로 올라가든 아래로 내려가든 차이가 없게 된다!
이게 무슨 말인지 아래 코드를 보면 좀 더 이해가 잘 될 듯하다.

for(int i=0; i<m; i++){
            stk = new StringTokenizer(bfr.readLine());
            int parent = Integer.parseInt(stk.nextToken());
            int child = Integer.parseInt(stk.nextToken());
            map[parent][child] = 1; \\ 
            			    양 방향 모두!!
            map[child][parent] = 1; //
        }

아래는 내가 제출한 코드다.

import java.util.*;
import java.io.*;

public class boj2644 {
    static int n,m, p1,p2;
    static int[][] map;
    static boolean[] visited;

    public static void main(String args[]) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk = new StringTokenizer(bfr.readLine());
        n = Integer.parseInt(stk.nextToken());
        map = new int[n+1][n+1];    visited = new boolean[n+1];
        stk = new StringTokenizer(bfr.readLine());
        p1 = Integer.parseInt(stk.nextToken()); p2 = Integer.parseInt(stk.nextToken());
        stk = new StringTokenizer(bfr.readLine());
        m = Integer.parseInt(stk.nextToken());
        for(int i=0; i<m; i++){
            stk = new StringTokenizer(bfr.readLine());
            int parent = Integer.parseInt(stk.nextToken());
            int child = Integer.parseInt(stk.nextToken());
            map[parent][child] = 1;
            map[child][parent] = 1;
        }

        bfw.write(String.valueOf(bfs(p1,p2)));
        bfw.close();
    }

    static Integer bfs(int p1, int p2){
        int result = 0;
        Queue<Integer> q = new LinkedList<>();
        q.add(p1);

        while(!q.isEmpty()){
            int size = q.size();
            for(int i=0; i<size; i++){
                int cur = q.poll();
                visited[cur] = true;
                if(cur==p2) return result;
                for (int child = 1; child <= n; child++) {
                    if (map[cur][child] == 1) {
                        if (!visited[child])
                            q.add(child);
                    }
                }
            }
            result++;
        }
        return -1;
    }
}