[백준] 2644번. 촌수 계산 (JAVA)

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

---

문제

---

풀이

import java.io.*;
import java.util.*;
public class Main {
    static int[][] arr;
    static boolean[] visited;
    static int n, cnt, ans;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());

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

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

        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        int line = Integer.parseInt(br.readLine());

        for(int i = 0; i < line; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) ;
            int y = Integer.parseInt(st.nextToken());
            arr[x][y] = arr[y][x] = 1;
        }

        ans = -1;
        dfs(start, end);
        System.out.println(ans);
    }

    public static void dfs(int start, int end){
        if(start == end){
            ans = cnt;
            return;
        }

        visited[start] = true;
        for(int i = 0; i <= n; i++){
            if(arr[start][i] == 1 && !visited[i]){
                cnt++;
                dfs(i , end);
                cnt--;
            }
        }
    }
}

 

간단한 dfs문제이다. 구현 중에 헷갈렸던 부분은 cnt--;를 안 넣었던 것이다. 이는 탐색 순서에 대한 오류가 발생할 수 있어서이다. 숫자의 크기에 따른 부모와 자식 간의 관계가 있는 것은 아니기에 3->4->2->5 일 수도 있지만 3->1->7->4(이건 3-1-7의 탐색이 끝난 뒤 다시 4로 돌아온 거라고 생각하자.) ->2->5 이런 식으로 끝났을 수도 있기 때문이다.

 

따라서 dfs를 돌리면서 (int start, int end, int cnt)와 같이 계속 뎁스를 가져가는 방식을 취하거나, cnt--를 통해 보정을 해주는 동작을 해야한다는 것이다.