최근에 올린 질문, 코드블럭으로 공유드립니다!

[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편

알고리즘 수업 - 깊이 우선 탐색 2 (백준 24480)

작성

import java.util.*;

public class Main {
    static int N, M, R;
    static int[] answer;
    static ArrayList<Integer>[] graph;
    static boolean[] visited;
    static int order = 1;
    
    public static void dfs(int idx) {
        visited[idx] = true;
        answer[order] = idx;
        order++;
        
        for(int i = 0; i < graph[idx].size(); i++) {
            if(!visited[graph[idx].get(i)])
               dfs(graph[idx].get(i));  
        }
    }
    
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        
        N = input.nextInt();
        M = input.nextInt();
        R = input.nextInt();
        
        answer = new int[N+1];
        visited = new boolean[N+1];
        graph = new ArrayList[N+1];
                
        for(int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }
        
        for(int i = 0; i < M; i++) {
            int x = input.nextInt();
            int y = input.nextInt();
            graph[x].add(y);
            graph[y].add(x);
        }
        
        for(int i = 1; i < graph.length; i++) {
            Collections.sort(graph[i], Collections.reverseOrder());
        }
        
        dfs(R);
        
        for(int i = 1; i < answer.length; i++) {
            System.out.println(answer[i]);
        }
        
    }
}

이렇게 구현한 경우, 틀렸다고 나오는데,
ide로 돌리고 출력해보면
1
4
3
2
0

으로 정상 출력되는데.. 이유를 모르겠습니다ㅠㅠ!

선생님이 작성해주신 코드

answer[idx] = order;
order++;

제가 작성한 코드

answer[order] = idx;
order++;

이렇게해도, 제가 하나씩 디버깅해서 따라가보면, 정답과 맞게 나오는데, 틀렸다고합니다.. !

java 코딩-테스트 알고리즘 dfs

답변 1

개발자로 취직하기

지식공유자

예현님 안녕하세요! 제 생각에는 출력해야 되는 내용을 잘못 이해하셔서 문제가 발생하는 것 같은데, 공교롭게도 예시에서는 그 차이가 뚜렷하게 보이지 않아서 헷갈리는 것 같습니다.

우선 문제에서 요구하는 건 '각 숫자가 출력된 순서' 이기 때문에, 우리가 배열에 담아야 하는 값은 '순서'이고, 담아야 할 배열의 위치(index)가 숫자가 되는 겁니다. 그래서 결과적으로 answer[2] = 4라고 한다면 2번 노드는 4번째 방문됐다 라는 것이 문제에서 요구한 것이고, 그래서 정답이 위에 말씀해주신 제 코드처럼 나오게 됩니다!

예현님께서 작성하신 코드는 반대로 '각 순서에 출력된 숫자'를 구현하셨기 때문에 배열에 담기는 값이 '숫자(idx)'이고, 위치가 순서가 됩니다.

한 가지 예시를 들자면, dfs 동작 상 노드 방문 순서가 다음 같다고 가정할게요: 1 -> 5 -> 2 -> 3 -> 4. 그러면 예현님 답은 이 순서 그대로 출력을 하겠지만, 문제에서 원하는 답은 1 3 4 5 2 가 될겁니다.

왜냐하면 1은 첫번째 방문했고, 2는 3번째 방분, 3은 4번째 방문, 이런 식이기 때문입니다!

결론은 코드는 문제가 없어보여서 잘 나오는데, 다만 문제에서 의도한 정답을 잘못 이해하셔서 그런 것 같습니다! 문제 다시 한번 확인해보시고 혹시 추가로 궁금한 점 있으면 말씀해주세요!!

김예현

질문자

감사합니다.. 이해했습니다 ㅜㅜ

개발자로 취직하기

지식공유자

네 감사합니다! 공부 화이팅하세요 :)

인프런 커뮤니티 질문&답변

최근에 올린 질문, 코드블럭으로 공유드립니다!