[백준] 16964번 DFS 스페셜 저지 풀어보기 [Java]

상대적으로 적은 사람이 푼 문제를 풀어서 뭔가 기분이 좋다.

그리고 오랜만에 1제출 1정답이여서 더 기분이 좋고,,,,

그래프가 주어지고, 해당 그래프를 정점 1 부터 시작해서, DFS로 탐색한 경로가 들어온다. 

우리가 찾아야 될 것은 해당 탐색 경로가 DFS로 탐색한 올바른 경로가 맞는지 체크를 하는 것이다. 어느 곳을 먼저 탐색할 지 모르기 때문에, DFS경로는 여러 경로가 나올 수 있다!!

 

👨‍🏫  풀이

일단, DFS로 진행하여, 해당 그래프의 누가 parent인지 확인을 하고, 자신의 child 수가 몇명인지 확인을 한다.

 

그리고 입력으로 들어온 Order를 앞에서부터 체크를 한다. 첫 parent는 무조건 1이기 때문에, 1로 설정한다.

현재 순서의 parent와 현재 parent로 설정된 것이 같은 것인지 확인한다. 만약 다르다면, 잘못된 경로로 0을 출력한다.

만약 같다면, parent의 childsize를 줄여준다.

그리고 현재 노드의 childsize가 0이 아니면, 현재 노드를 parent로 설정해준다.

만약 childsize가 0이라면, parent의 childsize가 0이 아닐때 까지, parent의 parent childsize를 확인해주고, parent의 childsize가 0이 아닌, node를 찾으면, 해당 node를 parent로 설정해준다.

 

👨🏻‍💻 코드

package 번16964;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static ArrayList<Integer>[] map;
    static int[] dfsOrder;
    static boolean[] isVisited;
    static class Node{
        int parent, childSize;

        public Node(){
            parent = 0;
            childSize = 0;
        }
        public Node(int parent, int childSize) {
            this.parent = parent;
            this.childSize = childSize;
        }
    }
    static Node[] nodes;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        map = new ArrayList[N+1];
        isVisited = new boolean[N+1];
        dfsOrder = new int[N+1];
        nodes = new Node[N+1];
        for(int i = 0 ; i <= N ; i++){
            map[i] = new ArrayList<>();
            nodes[i] = new Node();
        }

        for(int i = 0 ; i < N - 1 ; i++){
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken()); int n2 = Integer.parseInt(st.nextToken());
            map[n1].add(n2);
            map[n2].add(n1);
        }
        Arrays.fill(isVisited,false);
        dfs(1);
        st = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < N  ; i++){
            dfsOrder[i] = Integer.parseInt(st.nextToken());
        }
        int parent = 1;
        boolean isPossible = true;
        for(int i = 1 ; i < N ; i++){
            int cur = dfsOrder[i];
            if(nodes[cur].parent == parent){
                nodes[parent].childSize--;
                if(nodes[cur].childSize != 0){
                    parent = cur;
                } else if(nodes[cur].childSize == 0 && i != N - 1){
                    while(nodes[parent].childSize == 0){
                        parent = nodes[parent].parent;
                    }
                }
            }
            else{
                isPossible = false;
                break;
            }
        }
        if(isPossible) System.out.println("1");
        else System.out.println("0");
    }

    private static void dfs(int cur) {
        isVisited[cur] = true;
        for (Integer next : map[cur]) {
            if(isVisited[next]) continue;
            nodes[cur].childSize++;
            nodes[next].parent = cur;
            dfs(next);
        }
    }
}