[BOJ] 백준 2644 촌수계산

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

2644번: 촌수계산

 

---

 

풀이 방법

1. 예제로 나온 그래프를 그리면 이런 형태가 되는데, 시작점을 7로 잡고 끝점을 3으로 잡으면 이러한 방향 그래프가 나온다.
2. 정점 1번을 보면 들어오는 경우가 있고, 나가는 경우가 있으니 이것은 양방향 인접 리스트를 이용해서 풀 수 있다는 것을 알 수 있다.
3. dfs를 사용해서 시작점을 계속 바꿔주고, 시작점이 바뀔 때마다 count를 한다. 
4. 시작점과 끝점이 같아지는 경우에 count 를 리턴한다.

 

다음은 Java로 작성한 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class B2644 {
    private static ArrayList<ArrayList<Integer>> list;
    private static boolean [] visited;
    private static int answer = -1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        String [] str = br.readLine().split(" ");
        int num1 = Integer.parseInt(str[0]);
        int num2 = Integer.parseInt(str[1]);

        int m = Integer.parseInt(br.readLine());

        list = new ArrayList<>();
        visited = new boolean[n+1];

        for (int i = 0; i <= n; i++) {
            list.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) { // 양방향 인접 리스트
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            list.get(x).add(y);
            list.get(y).add(x);
        }

        dfs(num1, num2, 0);

        System.out.println(answer);
    }

    private static void dfs(int start, int end, int count) {
        visited[start] = true;

        for (int i: list.get(start)) {
            if (!visited[i]) {
                if (i == end) {
                    answer = count + 1;
                    return;
                }

                dfs(i, end, count+1);
            }
        }
    }
}