안녕하세요, 혹시 다른문제도 여쭤볼 수 있을까요?

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

해결된 질문

작성

import java.util.*;

public class Main {
    static int N;
    static ArrayList<Integer>[] graph;
    static ArrayList<Integer>[] graphReverse;
    static ArrayList<Integer> orderNode = new ArrayList<>();
    static ArrayList<Integer> reverseOrderNode = new ArrayList<>();
    static boolean[] visited;

    public static void dfs(int idx) {
        visited[idx] = true;
        orderNode.add(idx);

        for(int next : graph[idx]) {
            if(!visited[next]) {
                dfs(next);
            }
        }
    }

    public static void dfsReverse(int idx) {
        visited[idx] = true;
        reverseOrderNode.add(idx);

        for(int next : graphReverse[idx]) {
            if(!visited[next]) {
                dfsReverse(next);
            }
        }
    }

    public static void main (String[] args) {
        Scanner input = new Scanner(System.in);
        boolean isReverseOrder = true;
        boolean isOrder = true;
        N = input.nextInt();

        graph = new ArrayList[N+1];
        graphReverse = new ArrayList[N+1];
        visited = new boolean[N+1];

        for(int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
            graphReverse[i] = new ArrayList<>();
        }

        for(int i = 0; i < N-1; i++) {
            int x = input.nextInt();
            int y = input.nextInt();
            graph[x].add(y);
            graph[y].add(x);
            graphReverse[x].add(y);
            graphReverse[y].add(x);
        }
        input.nextLine();
        String[] orderStr = input.nextLine().split(" ");
        
        for(int i = 1; i <= N; i++) {
            Collections.sort(graphReverse[i], Collections.reverseOrder());
        }

        for(int i = 1; i <= N; i++) {
            if(!visited[i]) {
                dfs(i);
            }
        }

        visited = new boolean[N+1];

        for(int i = 1; i <= N; i++) {
            if(!visited[i]) {
                dfsReverse(i);
            }
        }

        for(int i = 1; i <= orderStr.length; i++) {
//            System.out.println(orderStr[i-1]);

            if(reverseOrderNode.get(i-1) != Integer.parseInt(orderStr[i-1])) {
                isReverseOrder = false;
            }
            if(orderNode.get(i-1) != Integer.parseInt(orderStr[i-1])) {
                isOrder = false;
            }

        }
        if(isOrder || isReverseOrder) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }
}

안녕하세요 강사님,,
덕분에 비전공자인 제가 dfs 26개의 문제를 풀고 골드에 진입했습니다.
정말 너무나도 감사합니다.

하지만 골드에서 막히는게 많은데 이번 문제는 도저히 검색하고,
반례를 다 찾아보고 해봐도 해결이 되지않아 답답한 마음에 여기에 글을 적습니다..

문제는 백준 https://www.acmicpc.net/problem/16964 DFS 스페셜 저지입니다.

제가 푼 방법은 2개의 그래프를 만든 후,
1개는 sort, 다른 한개는 reverseOrder을 하여,

정점 방문 순서를 2개 구한 후,

마지막에 제시되는 4개의 숫자와 비교하여 출력하는 방식으로 코드를 작성하였습니다.

하지만 제가 찾아본 모든 반례와 백준에서 제공되는 예제들은 통과되는데,

6%에서 틀렸다고 나옵니다.

다른문제로 곤란하게 해드렸다면, 바로 글 삭제하겠습니다.

감사합니다.

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

답변 1

개발자로 취직하기

지식공유자

안녕하세요 김예현님!

강의가 도움 되셨다니 다행입니다. 원래는 다른 문제 답변은 못 드리는데, 이번 문제는 저도 이미 풀었던 문제라 간단하게 답변 드리겠습니다 🙂

작성하신 코드에 따르면 DFS 순서와 입력 순서가 정확히 일치하는 경우에는 정답이 나오지만, 둘이 일치하지 않을 경우에는 오답이 나올 수 있을 것 같아요. 트리 구조는 고려하지 않는 단순 비교 방식이라 둘이 같아야만 1을 출력하여 오답이 되지 않을까 싶습니다.

제 생각에 더 나은 답안은 DFS를 사용해서 트리 구조를 분석하고, 서브트리 크기와 깊이를 고려해야 입력 순서가 달라지더라도 트리 구조상 유효한지 아닌지를 판단하고 1 혹은 0을 제대로 출력할 수 있을 것 같습니다!

제 답안 참고로 보내드리니 DFS 순서와 입력 순서가 다른 경우를 두 코드로 돌려보시면서 차이를 보셔도 이해에 도움 될 것 같습니다. 공부 화이팅하세요!

import java.util.*;

public class Main {
    static int N;
    static ArrayList<Integer>[] graph;
    static boolean[] visited;
    static int[] level, tsize;
    static int[] order;

    public static int dfs(int node, int lv) {
        if (visited[node]) return 0;
        visited[node] = true;
        level[node] = lv;
        int size = 1;
        for (int next : graph[node]) {
            size += dfs(next, lv + 1);
        }
        tsize[node] = size;
        return size;
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        N = input.nextInt();

        graph = new ArrayList[N + 1];
        visited = new boolean[N + 1];
        level = new int[N + 1];
        tsize = new int[N + 1];
        order = new int[N];

        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < N - 1; i++) {
            int x = input.nextInt();
            int y = input.nextInt();
            graph[x].add(y);
            graph[y].add(x);
        }

        for (int i = 0; i < N; i++) {
            order[i] = input.nextInt();
        }

        if (order[0] != 1) {
            System.out.println(0);
            return;
        }

        dfs(1, 0);

        for (int i = 1; i < N; i++) {
            int node = order[i];
            if (tsize[node] == 1 || i + tsize[node] >= N) continue;

            int next = order[i + tsize[node]];
            if (level[next] > level[node]) {
                System.out.println(0);
                return;
            }
        }

        System.out.println(1);
    }
}

김예현

질문자

너무 감사합니다 강사님...

개발자로 취직하기

지식공유자

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

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

안녕하세요, 혹시 다른문제도 여쭤볼 수 있을까요?