[JAVA] DFS,재귀 이해하기/ 백준 2644 촌수계산

 

 

나는 DFS로 풀었다

 

 

 

 

처음에 작성한 코드

 

public class Baek_2644 {
    static int[][] family;
    static boolean[] check;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int A = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int S = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        int N = Integer.parseInt(br.readLine());
        family = new int[A+1][A+1];
        check = new boolean[A+1];

        while (N-->0){
            st = new StringTokenizer(br.readLine()," ");
            int a= Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            family[a][b] = family[b][a] =1;
        }
        System.out.println(cd(S,E,0));


    }
    static int cd(int start,int end,int cnt){
        if(start==end) return cnt;
        check[start] = true; //방문했다고 표시하고
        for(int i=1; i< check.length; i++){
            if(family[start][i]==1&&!check[i]){ //start와 연결되어있으면서 방문하지 않았다면
                check[i] = true;
                return cd(i,end,cnt+1);
            }
        }
        return -1;
    }
}

그러나 예상과는 다르게 어떠한 경우에도 -1이 출력되었다

 

 

위 코드는 재귀호출 결과를 바로 반환한다. 

따라서 재귀 호출 결과가 -1이 아닌 경우에도 더 이상 반복하지 않고 즉시 -1을 반환하므로, 시작점과 도착점 사이의 경로가 여러 개 있을 때, 모든 경로를 찾아낼 수 없다.

 

따라서 temp에 cd값을 저장해주고 -1이 아닐 경우에 cd값을 리턴해주는 식으로 변경하였다

이렇게 하면 -1이 아닌 경우에는 재귀 호출을 반복하여 cnt값을 제대로 계산하여 return할 수 있다.

 

 

 

 

 

cd메서드에 다음과 같이 반환하기 전 재귀 호출의 결과가 -1인지 확인하는 로직을 추가하였고,

문제를 해결할 수 있었다

    static int cd(int start,int end,int cnt){
        if(start==end) return cnt;
        check[start] = true; //방문했다고 표시하고

        for(int i=1; i< check.length; i++){
            if(family[start][i]==1&&!check[i]){ //start와 연결되어있으면서 방문하지 않았다면
                check[i] = true;
                int temp = cd(i,end,cnt+1);
                if(temp!=-1) return temp;
            }
        }

        return -1; //start와 end도 아니고(찾지 못했고) 더이상 연결된 노드도 없다면 -1 return
    }
}