BOJ_S2_2644

📁 [S2_2644] 촌수계산

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

public class Main {
    static StringTokenizer st;
    static int[][] arr;
    static boolean[][] v;
    static int cnt, res;
    static int n;
    static int res_start, res_end;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // 전체 사람의 수
        n = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine(), " ");

        // 계산해야하는 촌수
        res_start = Integer.parseInt(st.nextToken());
        res_end = Integer.parseInt(st.nextToken());

        // 관계의 개수
        int m = Integer.parseInt(br.readLine());

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

        v = new boolean[n+1][n+1];

        res  = 0;

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

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            arr[start][end] = arr[end][start] = 1;
        }

        dfs(res_start);


        if(res == 0){
            sb.append(-1);
        }
        else {
            sb.append(res);
        }
        System.out.println(sb);

    }

    static void dfs(int start){
        // 기저 조건
        if(start == res_end){
            res = cnt;
            return;
        }

        for(int i=1; i<n+1; i++){
            if(arr[start][i] == 1 && !v[start][i]){
                // 방문 처리
                v[start][i] = v[i][start] = true;
                cnt++;
                dfs(i);
                cnt--;
            }
        }
    }
}

🤔 나의 생각

이 문제는 처음 보고 집합으로 풀어야 하나 라고 생각을 했는데 트리를 그려보니 위는 1촌 이고 옆은 2촌인데 옆도 결국 펼쳐보면 위로 한 칸 갔다가 다시 밑으로 가는 거여서 그냥 경로의 길이를 구해주면 되는 것이였다.
그래서 dfs 알고리즘을 이용해서 깊이 우선 탐색을 해주었다.
그리고 방향성이 없기 때문에 입력을 받을 때 양 방향 다 해주었다.
문제에서 경로의 길이를 구해야하는 것을 안다면 어렵지 않게 구현할 수 있었을 거다.