[BOJ] 백준 2644 - 촌수 계산 (자바)

BFS를 통해 푸는 문제이다. 물론 DFS로 문제를 풀 수 있을 것 같다.

나는 세가지 변수를 설정했다.

1. 1촌 관계를 저장하는 배열 : Arr[][2]

2. 방문했던 점을 저장하는 배열 : visited[]

3. 얼마만큼 지나왔는지 저장하는 배열 : total[]

세가지만 이용하면 쉽게 문제를 풀 수 있다.

import java.io.FileInputStream;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
    static int[][] arr;
    static boolean[] visited;
    static int[] total;
    static int x;
    static int y;
 
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(new FileInputStream("input.txt"));
        int N = sc.nextInt();
        arr = new int[N + 1][2];    //1촌관계를 저장할 배열
        visited = new boolean[N + 1];    // 방문했던 값을 다시 방문하면 무한루프에 빠지게 된다.
        total = new int[N + 1];        //몇칸을 거쳐왔는지에 대한 배열
        x = sc.nextInt();        //입력 X값
        y = sc.nextInt();        //입력 Y값
 
        
        int K = sc.nextInt();
        for (int i = 1; i <= K; i++) {
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }
        System.out.println(BFS(x, N));
    }
 
    public static int BFS(int x, int N) {
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(x);
        //큐가 비었으면 연결이 끊어졌다는 소리이다.
        while (!q.isEmpty()) {
            int nextX = q.poll();
            visited[nextX] = true;
            //방문한 점은 true로 바꿈으로써 재방문 하지 안도록 한다.
            for (int i = 0; i < N; i++) {
                //전체 배열을 돌면서 연결되있으면서 방문 안한점이 있나 체크한다
                //있다면 큐에 넣어준다.
                if (arr[i][0] == nextX && !visited[arr[i][1]]) {
                    //1촌관계가 랜덤으로 되어있으므로 왼쪽 라인 한번
                    q.add(arr[i][1]);
                    //이전에서 +1 된 값을 저장한다
                    total[arr[i][1]] = total[arr[i][0]] + 1;
                } else if (arr[i][1] == nextX && !visited[arr[i][0]]) {
                    //오른쪽 라인 한번
                    q.add(arr[i][0]);
                    //이전에서 +1된값을 저장한다.
                    total[arr[i][0]] = total[arr[i][1]] + 1;
                }
            }
            //q가 비었거나 찾는값이 있으면 종료한다.
            if (!q.isEmpty() && q.peek() == y) {
                return total[y];
            }
 
        }
        return -1;
    }
}
 

문제에 나와있지 않은 예시를 하나 들자면.

10

7 6

9

1 2

1 3

1 4

9 1

9 10

3 5

3 6

2 7

2 8

이 있다. 이때의 결과값은 4가 나와야 한다.