[백준 알고리즘] 2644번 촌수 계산(Java) 문제 풀이

문제

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

2644번: 촌수계산

문제에 대한 이해

이 문제를 보자마자, 그래프탐색이 떠올랐고, 촌수라는 개념에서 리스트를 사용함과 그리고 DFS를 통해서 촌수를 계산해야겠다고 생각했다. 이유는 촌수라는 개념에서 그래프가 떠올랐고 주어진 두사람의 촌수를 나타내는 정수에서 DFS를 통한 그래프 탐색을 이용하여 문제의 정답을 탐색하여 찾아나아가면서 촌수를 +1 씩하면 되겠다고 생각했다.

어떻게 풀 것인가?

DFS도 인접행렬과 인접리스트 2가지 방식으로 풀 수 있는데, 위와같은 방식은 인접리스트 방식으로 풀어야한다.

주어진 촌수들을 하나하나 인접리스트에 삽입하여 아래와 같은 그림방식으로 트리와 같은 형태로 만든 후, DFS을 이용하여 문제를 풀면 간단하게 풀린다.

 

https://loosie.tistory.com/165

[BOJ] 백준 2644번 촌수계산 (Java)

그림의 출처는 여기이다.

시간복잡도

DFS의 탐색 시간은 O(N)이다.

공간복잡도

리스트에 대한 생각만 하면 된다. O(V)

풀면서 놓쳤던점

처음에는 너무 기계적으로 풀려고 생각했다.

이 문제를 통해 얻어갈 것

인접리스트를 통한 DFS풀이

내 코드 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

// 백준알고리즘 2644번 촌수 계산

public class Main {
    static int ans = -1;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

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

        st = new StringTokenizer(br.readLine());
        int findX = Integer.parseInt(st.nextToken());
        int findY = Integer.parseInt(st.nextToken());

        ArrayList<ArrayList<Integer>> a = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            a.add(new ArrayList<>());
        }

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

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

        boolean[] visited = new boolean[N + 1];
        DFS(a, visited, findX, findY, 0);

        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    // DFS를 이용하여 촌수 계산.
    public static void DFS(ArrayList<ArrayList<Integer>> a, boolean[] visited, int pos, int find, int cnt) {
        visited[pos] = true;

        for (int i : a.get(pos)) {
            if (!visited[i]) {
                if (i == find) { // 찾으려는 사람의 도달.
                    ans = cnt + 1;
                    return;
                }

                DFS(a, visited, i, find, cnt + 1);
            }
        }
    }

}