[Baekjoon] 2644 - 촌수계산

📝 문제

 

 

🔑 풀이 과정

예제 입력1, 2의 촌수관계를 그래프로 나타내면 다음과 같다. (예제1, 2 동일)

여기서 a에서 b까지 갈 때의 간선의 수가 a와 b의 촌수이다.

예제 1) 7과 3의 촌수는? 3

예제 2) 8과 6의 촌수는? 친척 관계가 전혀 없음.

 

① DFS를 사용해서 풀이를 진행한다.

 

② DFS를 진행할 때, 방문 정점만을 가지는게 아니라, 현재 깊이인 depth 인자를 추가해준다.

깊이는 시작 노드가 0이고, 선을 하나 건널때 마다 1씩 증가시킨다.

그림 참고(시작이 7, 도착이 3일 때의 답은 3)

 

③ DFS를 진행하다가, 도착노드에 도달하면 현재 depth를 출력한다. 만약 관계가 없으면 -1을 출력한다.

 

 

 

🔓 답안

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

public class Main {

    static int n, from, to;
    static int depth = 0;
    static int[][] matrix;
    static boolean[] visited;
    static int answer = -1;

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

        //첫째 줄 입력, 인접 행렬, 방문 배열 크기 지정
        n = Integer.parseInt(br.readLine());
        matrix = new int[n+1][n+1];
        visited = new boolean[n+1];

        //두번째 줄 입력
        st = new StringTokenizer(br.readLine());
        from = Integer.parseInt(st.nextToken());
        to = Integer.parseInt(st.nextToken());

        //세번째 줄 입력
        int m = Integer.parseInt(br.readLine());

        //m개의 관계 입력받기, 인접행렬에 추가
        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            matrix[x][y] = 1;
            matrix[y][x] = 1;
        }

        answer = -1;

        DFS(from, depth);

        bw.write(answer + "\n");
        bw.flush();
        bw.close();

    }

    static void DFS(int s, int d){
        if(s == to){
            answer = d;
            return;
        }

        if(visited[s]){
           return;
        } else{
            visited[s] = true;
            for(int i = 1; i <= n; i++){
                if((matrix[s][i] == 1) && (visited[i] == false))
                    DFS(i, d+1);
            }
        }
    }

}

 

 

 

🖤 알고리즘 분류

- 그래프 이론

- 그래프 탐색

- 너비 우선 탐색

- 깊이 우선 탐색