(BOJ) 2644_촌수계산_JAVA

 

https://www.acmicpc.net/problem/2644

2644번: 촌수계산

<풀이>

BFS를 활용한 문제.

부모 자식 관계가 주어지면 각각의 리스트에 값을 넣어준다. 예를 들어 1 2를 입력 받으면 1번 리스트에 2를 넣어주고 2번 리스트에 1을 넣어준다.

이와 같이 입력 받으면 n번 리스트에 n번 사람과 1촌 관계에 해당하는 사람의 번호가 들어있게 된다.

문제의 예제를 입력 받으면 다음과 같다.

촌수를 계산해야 하는 두 사람의 번호는 7 3이다. 7에서부터 시작해서 관계를 찾아보자.

* (n번 사람, 7번과의 촌수)을 의미

먼저, 7번 리스트에 있는 2가 (2, 1)의 형태로 큐에 들어간다.

다음은 2번 리스트에 있는 1, 8, 9가 (1, 2) / (8, 2) / (9, 2)의 형태로 큐에 들어간다. (7은 방문했으므로 큐에 들어가지 않는다.)

다음으로 1번 리스트에 있는 3이 (3, 3)의 형태로 큐에 들어간다. (2는 방문했으므로 큐에 들어가지 않는다.)

이와 같은 행위를 반복하다가 3을 만나면 촌수를 출력하고 프로그램을 종료한다.

큐를 다 돌았는데 y번 사람을 찾지 못했다면 촌수 계산이 불가능하다는 뜻이므로 -1을 출력한다.

8번과 9번의 리스트가 뒤에 추가되어야 하지만 그림에는 생략했다(어차피 2번은 이미 방문했으므로 큐에 추가되지 않는다!)

<코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class BOJ_2644_촌수 {
    static int N; // 전체 사람의 수
    static int x, y; // 촌수를 계산해야 하는 서로 다른 두 사람의 번호
    static boolean visited[]; // n번 사람을 방문했는가 여부
    
    // Queue에 사용할 클래스
    static class Chon {
        int next;
        int cnt;
        Chon(int next, int cnt) {
            this.next = next;
            this.cnt = cnt;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        x = Integer.parseInt(st.nextToken());
        y = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(br.readLine());
        List<List<Integer>> li = new ArrayList<List<Integer>>();
        
        // 0 ~ N
        for (int i = 0; i <= N; i++) {
            li.add(new ArrayList<Integer>());
        }
        visited = new boolean[N + 1];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            // a번의 1촌에 b를 추가해주고 b번의 1촌에 a를 추가해준다.
            li.get(a).add(b);
            li.get(b).add(a);
        }
        Queue<Chon> q = new LinkedList<Chon>();
        visited[x] = true; // x번 사람 방문 표시
        // x번 사람의 1촌을 먼저 큐에 집어넣는다.
        for (int e : li.get(x)) {
            q.add(new Chon(e, 1));
            visited[e] = true;
        }
        while (!q.isEmpty()) {
            Chon c = q.poll();
            
            // y를 발견하면 계산된 촌수를 출력하고 프로그램 종료
            if (c.next == y) {
                System.out.println(c.cnt);
                System.exit(0);
            }
            
            for (int e : li.get(c.next)) {
                if (visited[e])
                    continue;
                q.add(new Chon(e, c.cnt + 1));
                visited[e] = true;
            }
        }
        
        // 큐를 다 돌았으나 촌수를 찾지 못했으면 -1 출력
        System.out.println("-1");
        
    } // end of main
}