2644번. 촌수계산

 

 

아이디어

입력을 토대로 정점 간의 연결 관계를 표현한 그래프를 만들고 촌수를 구해야 하는 대상(시작점)에서 dfs 를 수행한다.

 

dfs 를 수행했을 때 촌수를 구해야 하는 대상(끝점)에 도달하면 현재까지의 depth 를 계산해서 촌수를 출력하면 되고 만약 도달하지 못하면 -1 을 출력하면 된다.

 

 

풀이코드

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

public class Main {

    static int target1;
    static int target2;

    static int[][] graph;
    static boolean[][] visited;

    static int n;

    static int result = -1;

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

        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        target1 = Integer.parseInt(st.nextToken()) - 1;
        target2 = Integer.parseInt(st.nextToken()) - 1;

        int m = Integer.parseInt(br.readLine());
        graph = new int[n][n];

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;

            graph[a][b] = 1;
            graph[b][a] = 1;
        }

        visited = new boolean[n][n];
        dfs(target1, 0);

        System.out.println(result);
    }

    public static void dfs(int i, int depth) {
        if (i == target2) {
            result = depth;
            return;
        }

        for (int k = 0; k < n; k++) {
            if (graph[i][k] == 1 && !visited[i][k]) {
                visited[i][k] = true;
                visited[k][i] = true;

                dfs(k, depth + 1);
            }
        }
    }
}