백준 2644번 : 촌수계산 자바

🧫 문제 분석

 

✔️ 출처

촌수계 실버 2

 

📖 문제

 

1. bfs는 가중치가 같으면 항상 최단거리이다.
2. 그래프는 연결되어있기에 어디에서 시작하든지 가중치가 같다면 거리는 같다. (양방향 한정)
3. BFS는 재귀로 구현하지 못한다.

 

처음에는 진입 경로가 0인 최상위 부모를 찾아서 위에서부터 DFS 탐색으로 깊이를 측정하며 x와 y를 구했다.

부모와의 관계를 문자열로 저장하고 각 각 비교하면서 촌수를 따졌는데 이렇게하면 너무 오래걸리고, 이상하게 중복이 생겼다. 푸는 방향이 잘못되었던 것이다. 이 문제에서 원하는건 그래프와 넓이 탐색에 대한 개념을 잘 이해하는지를 물어보는 문제였고 나는 제대로 이해하지 못했어서 이상하게 풀이를 시작한 것이다. 

 

잘 기억하자. 

 

 

---

🔅 문제 풀이

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

public class Main {
    static boolean[][] kinship;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        // 관계를 찾는 번호
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());

        // 부모 자식들 간의 관계의 개수
        int m = Integer.parseInt(br.readLine());

        kinship = new boolean[n + 1][n + 1];
        visited = new boolean[n + 1];

        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            int parent = Integer.parseInt(st.nextToken());
            int child = Integer.parseInt(st.nextToken());

            kinship[parent][child] = true;
            kinship[child][parent] = true;
        }

        int answer = bfs(x, y);
        bw.write((answer == 0 ? -1 : answer) + "\n");
        bw.flush();
        bw.close();

    }

    private static int bfs(int dest, int idx) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {idx, 0});
        visited[idx] = true;

        while (!q.isEmpty()) {

            int[] poll = q.poll();
            int num = poll[0];
            int level = poll[1];

            if (num == dest) {
                return level;
            }

            for (int i = 1; i < kinship.length; i++) {
                if (kinship[num][i] && !visited[i]) {
                    q.add(new int[] {i, level + 1});
                    visited[i] = true;
                }
            }
        }
        return 0;
    }
}

 

 

 

❗ 오답노트 / 필요한 지식

1. 최솟값을 찾을 때 큰 값을 처리해주는 로직을 먼저 두자.
2. 그 외에도 항상 큰 값 먼저 처리하고 그 후에 작은 것을 처리