[ 백준 16964 ] - DFS 스페셜 저지(Java)

 

16964번: DFS 스페셜 저지

 

문제 이해 & 기본 개념

• 그래프와 방문 순서가 주어진다.
• 해당 그래프에서 입력받은 순서가 dfs로 방문 가능한지를 체크하는 문제
• 해당 문제는 방문 순서에 대한 기준을 두지 않았다.
• 즉, 어떤 순서로 방문을 해도 dfs로 방문 가능한 순서이기만 하면 된다.

---

중요 포인트

• n이 10만까지 들어오므로, dfs를 완전히 수행하면 시간 초과
• dfs로 접근하되, 수행 시간을 줄여아한다.

---

최종 풀이

• dfs의 경우 여러 자식들 중 어떤 자식을 먼저 방문하냐에 따라 방문 순서가 달라진다.
• 해당 문제에서는 현재 노드의 자식들 모두에 대해 방문해야할 노드가 있는지 체크한 후 방문하면 된다.

1. 현재 노드의 자식들을 HashSet에 저장한다. (부모는 제외, 양방향 그래프이므로 자식 리스트에 부모도 같이 존재)
2. 만약 현재 노드가 Leaf라면 (자식이 없는 경우, set의 크기가 0) return
3. 다음 방문 순서의 노드가 현재 노드의 자식이고, 방문하지 않았다면 재귀를 통해 해당 노드를 방문한다.
4. 현재 노드의 모든 자식 수만큼 반복 (예시 참조)

그래프 예시

• 해당 그래프에서 1-3-5-8로 방문했을 경우, 다시 3번에서 2번과 6번을 방문해야한다.
• 즉, 한 노드에선 무조건 자식 갯수만큼은 방문을 하게 됨
• 따라서, 아래와 같이 len(자식의 개수)만큼 반복문을 통해 노드를 방문한다.
• 만약 아래의 dfs에서 해당 노드의 자식을 방문하고 돌아왔다면, 그 노드는 건너뛸 수 있게 된다.

        // 현재 노드의 자식들을 통해서 다음 order로 갈 수 있는지만 체크하는 반복문
        while(len > 0){ 
            int next = order[idx];
            // 현재 노드에서 다음 order로 갈 수 있는 자식이 있으면 dfs 진입
            if(!node[next].visited_ && set.contains(next)){
                idx++;
                node[next].visited_ = true;
                dfs(curNode, next); 
                len--;
            }
            else break; // 없으면 바로 종료
        }

---

주의 할 점

• 해당 문제에선 양방향 그래프가 들어온다.
• 단방향 그래프라고 생각하고 풀면 틀릴 수 있다.

---

 

소스 코드

class Node{
    boolean visited_ = false;
    HashSet<Integer> child = new HashSet<>();
}

public class Main {
    public static Node[] node;
    public static int[] order;
    public static int n, idx = 1;
        
    public static void dfs(int parent, int curNode){
        HashSet<Integer> set = new HashSet<>();
        for (Integer i : node[curNode].child) if(i != parent) set.add(i);
        
        int len = set.size();
        if(len == 0) return;
        
        // 현재 노드의 자식들을 통해서 다음 order로 갈 수 있는지만 체크하는 반복문
        while(len > 0){ 
            int next = order[idx];
            // 현재 노드에서 다음 order로 갈 수 있는 자식이 있으면 dfs 진입
            if(!node[next].visited_ && set.contains(next)){
                idx++;
                node[next].visited_ = true;
                dfs(curNode, next); 
                len--;
            }
            else break; // 없으면 바로 종료
        }
    }
    
    public static void main(String[] args) throws IOException {
        // TODO code application logic here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        node = new Node[n + 1];
        
        for (int i = 0; i < n+1; i++) node[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());
            if(!node[n1].child.contains(n2)) {
                node[n1].child.add(n2);
                node[n2].child.add(n1);
            }
        }
        
        String[] input = br.readLine().split(" ");
        
        order = new int[n];
        for(int i = 0; i < input.length; i++) 
            order[i] = Integer.parseInt(input[i]);
        
        if(order[0] == 1){
            node[1].visited_ = true;
            dfs(-1, 1);
        }
        
        System.out.println((idx == n ? 1 : 0));
    }
}

 

---

시도 방법 1 (35% 시간 초과)

• 스택을 이용하여 방문하는 모든 경로를 체크했다.
• 이전 경로를 기록하고 더 이상 갈 수 없으면 다시 돌아가는 방법ㅋ
• 시간 초과 안나는게 이상한 코드였다.

class Node{
    int index_;
    boolean visited_ = false;
    ArrayList<Integer> child = new ArrayList<>();

    public Node(int index_) {
        this.index_ = index_;
    }
}

public class Main {
    public static Node[] node;
    public static int n;
    
    public static boolean isCorrectOrder(int[] order, int n){
        if(order[0] != 1) return false;
        node[1].visited_ = true;
        
        int index = 1;  
        int cur = 1;    // 현재 방문 중인 노드
        Stack<Integer> prevStack = new Stack();
        
        while(index < n){
            // 다음 노드가 현재 노드와 연결되어 있고 방문하지 않은 노드인 경우
            int next = order[index];
            if(node[cur].child.contains(next) && !node[next].visited_) { 
                prevStack.push(cur); // 다음 노드로 이동
                node[cur = next].visited_ = true;
                index++;
            } 
            else {
                /**
               * else에 들어오면 현재 노드에서 다음 노드로 갈 수 없다는 소린데, 
               * stack이 비어있으면 더 올라갈 수도 없다는 뜻이므로 올바른 순서가 아님
               */
                if(prevStack.isEmpty()) return false; 
                while(!node[cur].child.contains(order[index]) && !prevStack.isEmpty()){
                    cur = prevStack.pop();
                }
            }
        }
        
        return true;
    }
        
    public static void main(String[] args) throws IOException {
        // TODO code application logic here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        node = new Node[n + 1];
        
        for (int i = 0; i < n + 1; i++) node[i] = new Node(i);
        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());
            if(!node[n1].child.contains(n2)) {
                node[n1].child.add(n2);
                node[n2].child.add(n1);
            }
        }
        
        String[] input = br.readLine().split(" ");
        int[] order = new int[n];
        for(int i = 0; i < input.length; i++){
            order[i] = Integer.parseInt(input[i]);
        }
        
        if(isCorrectOrder(order, n)) System.out.println("1");
        else System.out.println("0");
    }
}

 

---

 

시도 방법 2 (72% 시간 초과)

• Depth를 통해 올바른 순서인지 판단하는 방법을 시도해봤다.
• dfs를 한 번 수행하여 노드들의 depth를 체크하고, 방문 순서에서 depth가 이어지지 않으면 해당 노드의 자식이 있는지 확인한다.
• 자식이 있다면, 끝까지 이어지지 않은 것이므로 올바르지 않은 순서

=> 여전히 dfs를 한 번은 수행하므로 시간 초과

class Node{
    int depth = 0;
    boolean visited_ = false;
    ArrayList<Integer> child = new ArrayList<>();
}

public class Main {
    public static Node[] node;
    public static int n;
    
    public static void dfs(int idx, int depth){
        if(node[idx].visited_) return;
        
        node[idx].depth = depth;
        node[idx].visited_ = true;

        for (Integer child : node[idx].child){
            if(!node[child].visited_) dfs(child, depth + 1);
        }
    }
        
    public static boolean isCorrectOrder(int[] order){
        if(order[0] != 1) return false;
        
        dfs(1, 1);

        for (int i = 0; i < order.length-1; i++) {
            int curDepth = node[order[i]].depth;
            int nextDepth = node[order[i+1]].depth;
            
            if(curDepth != 0 && curDepth+1 != nextDepth){
                // 양방향 그래프이므로 자신보다 깊은 노드가 있는지 확인
                for (Integer child : node[order[i]].child) {
                    if(curDepth < node[child].depth) return false;
                }
            }
        }
        int lastDepth = node[order[order.length-1]].depth;
        for (Integer child : node[order[order.length-1]].child) {
            if (lastDepth < node[child].depth) return false;
        }
        
        return true;
    }
    
    public static void main(String[] args) throws IOException {
        // TODO code application logic here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        node = new Node[n + 1];
        
        for (int i = 0; i < n+1; i++) node[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());
            if(!node[n1].child.contains(n2)) {
                node[n1].child.add(n2);
                node[n2].child.add(n1);
            }
        }
        
        String[] input = br.readLine().split(" ");
        
        int[] order = new int[n];
        for(int i = 0; i < input.length; i++) 
            order[i] = Integer.parseInt(input[i]);
        
        if(isCorrectOrder(order)) System.out.println("1");
        else System.out.println("0");
    }
}