백준 2644 풀이

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

이번 문제는 촌수를 찾는 문제다.

촌수 계산은 부자 관계는 1촌, 형제 관계는 2촌이다

이 생각을 바탕으로 문제를 풀어야는데 처음에는 트리로 구현하여 트리 순회를 통해 풀어야하나 생각을 했다.

트리로 생각해보면 문제를 어떻게 풀어야 할지 이해할 수 있었다.

촌수를 구해야 할 두 사람을 각각 출발지, 목적지로 정해 출발지에서 거쳐가는 간선의 수가 두 사람의 촌수가 된다.

1.방향이 없는 인접배열을 만들어 start를 시작으로 배열을 dfs로 탐색한다.
2.이렇게 하면 start가 포함된 트리 전체를 탐색
2-1.여기서 dest와 같은 index값을 찾을 수 있다면 촌수를 리턴
2-2.찾지 못하면 촌수 계산이 불가능하기때문에 -1을 리턴

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

public class Main {
    static int count = -1;
    static int[] dx = {-2, -2, -1, -1, 1, 1, 2, 2};
    static int[] dy = {1, -1, 2, -2, 2, -2, 1, -1};
    static boolean visited[];
    static int n, m;
    static int graph[][];

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

        graph = new int[n + 1][n + 1];

        visited = new boolean[n + 1];
        for (int i = 0; i < n; i++) {
            visited[i] = false;
        }

        String line = br.readLine();
        String[] l = line.split(" ");
        int a = Integer.parseInt(l[0]);
        int b = Integer.parseInt(l[1]);

        String k = br.readLine();
        int t = Integer.parseInt(k);
        for (int i = 0; i < t; i++) {
            String tmp = br.readLine();
            String[] point = tmp.split(" ");
            int x = Integer.parseInt(point[0]);
            int y = Integer.parseInt(point[1]);
            graph[x][y] = 1;
            graph[y][x] = 1;
        }
        dfs(a, b, 0);

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

    public static void dfs(int start, int dest, int cnt) {
        visited[start] = true;
        for (int i = 1; i <= n; i++) {
            if (graph[start][i] == 1 && !visited[i]) {
                if (i == dest) {
                    count = cnt + 1;
                    return;
                }
                dfs(i, dest, cnt + 1);
            }
        }
    }
}