[99클럽 코테 스터디 TIL#8일차] 백준 2644 촌수구하기

문제

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

 

 

문제 풀이

문제를 읽고 dfs 문제인거 알아서 dfs를 기본적으로 사용해서 풀었는데 다른 점과 놓친 점이 있었다.

다른 점 : cnt 를 계속 리셋해줘야한다 → 함수에 cnt를 인자로 넘기는 것으로 해결
놓친 점 : cnt를 인자로 넘기는 건 맞는데 실제 값을 증가시키면 안된다.

 

 

1. 틀린 코드

if (visited[n] == 0) {
    cnt++;
    dfs(n, cnt);
}

 

 

cnt++이 루프 안에서 실행되며, 참조값 cnt가 실제로 증가한다. 재귀 호출이 끝나고 돌아오면, cnt는 증가된 값으로 유지되며 다음 노드로 이동하는 문제가 있다.

 

 

2. 맞는 코드

if (visited[n] == 0) {
    dfs(n, cnt + 1);
}

 

cnt + 1 값을 새로운 재귀 호출에만 전달하고, 현재 호출에서의 cnt 값은 변경되지 않는다. 즉, 각 depth마다 독립적인 cnt 값을 가질 수 있다.

 

 

작성한 코드

import java.util.Scanner;
import java.util.ArrayList;

public class Main{
    
    public static int end;
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    public static int[] visited;
    public static int answer = -1;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int start = sc.nextInt();
        end = sc.nextInt();
        int m = sc.nextInt();
        
        visited = new int[n+1];
        
        for(int i = 0; i < n+1; i++) {
            graph.add(new ArrayList<>());
        }
        
        for(int i = 0; i < m; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            
            graph.get(x).add(y);
            graph.get(y).add(x);
        }
        
        dfs(start, 0);
        
        System.out.println(answer);
    }
    
    public static void dfs(int idx, int cnt) {
        visited[idx] = 1;
        
        if(idx == end) {
            answer = cnt;
            return;
        }
        
        for(int i = 0; i < graph.get(idx).size(); i++) {
            int n = graph.get(idx).get(i);

            if(visited[n] == 0){
                dfs(n, cnt+1);
            }
        }
    }
}