공부 192일차: 백준 16964번 DFS 스페셜 저지 자바 java

16964 DFS 스페셜 저지

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

16964번: DFS 스페셜 저지

 

 

 

 

---

백준 16964번 문제 DFS 스페셜 저지

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	4263	1473	1067	37.610%

문제

BOJ에서 정답이 여러가지인 경우에는 스페셜 저지를 사용한다. 스페셜 저지는 유저가 출력한 답을 검증하는 코드를 통해서 정답 유무를 결정하는 방식이다. 오늘은 스페셜 저지 코드를 하나 만들어보려고 한다.

정점의 개수가 N이고, 정점에 1부터 N까지 번호가 매겨져있는 양방향 그래프가 있을 때, DFS 알고리즘은 다음과 같은 형태로 이루어져 있다.

void dfs(int x) {
    if (check[x] == true) {
        return;
    }
    check[x] = true;
    // x를 방문
    for (int y : x와 인접한 정점) {
        if (check[y] == false) {
            dfs(y);
        }
    }
}

이 문제에서 시작 정점은 1이기 때문에 가장 처음에 호출하는 함수는 dfs(1)이다. DFS 방문 순서는 dfs함수에서 // x를 방문 이라고 적힌 곳에 도착한 정점 번호를 순서대로 나열한 것이다.

트리가 주어졌을 때, 올바른 DFS 방문 순서인지 구해보자.

입력

첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루어져 있으며, 1부터 N까지 자연수가 한 번씩 등장한다.

출력

입력으로 주어진 DFS 방문 순서가 올바른 순서면 1, 아니면 0을 출력한다.

제한

 

예제 입력 1

4
1 2
1 3
2 4
1 2 3 4

예제 출력 1

0

예제 입력 2

4
1 2
1 3
2 4
1 2 4 3

예제 출력 2

1

예제 입력 3

4
1 2
1 3
2 4
1 3 2 4

예제 출력 3

1

 

 

 

---

과정 생각해보기 & 오답

---

 

처음에 행렬로 선언했다가 계속 메모리 초과가 떴던 건 차치하고 오답부터!

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int n, idx; 
    static int result = 1;
    static ArrayList<Integer>[] list;
    static int[] store;
    static boolean[] visited;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        n = Integer.parseInt(br.readLine());
        list = new ArrayList[n];
        store = new int[n];
        visited = new boolean[n];
 
        for(int i = 0; i < n; i++) {            
            list[i] = new ArrayList<Integer>();
        }
        
        for(int i = 0; i < n-1; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken())-1;
            int y = Integer.parseInt(st.nextToken())-1;
            // 양방향
            list[x].add(y);
            list[y].add(x);
        }
        
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            store[i] = Integer.parseInt(st.nextToken())-1;
        }    
        
        dfs(0);
        System.out.println(result);
    }
 
    static void dfs(int x) {
        visited[x] = true;
        if(store[idx++] != x) {
            result = 0;
            return;
        }
        for(int val : list[x]) {
            if(!visited[val]) {
                dfs(val);
            }
        }
    }
}
 

 

오답인 이유는 아래와 같다

트리 구조인 이 문제에서, 1번부터 DFS 탐색을 시작할 때

2로 갈지, 3으로 갈지를 고를 수 있다

어느 것을 선택해도 깊이 우선 탐색이라는 사실은 변하지 않으므로 1 2 4 3 / 1 3 2 4 모두 가능하다

하지만 위의 코드는 한 가지 경우만 정답으로 친다는 문제점이 있다

(N과 M 문제처럼 모든 경우를 나열하는 방법도 있겠지만 시간 초과가 뜬다)

 

그래서 생각해볼 수 있는 방법은 가능한 자식 노드들의 경우를 저장하는 것!

이 블로그를 참고했다

 

 

 

---

정답 인정 코드

---

 

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int n;
    static int idx= 1; // 루트 다음 숫자부터 -> 2번째부터
    static int result = 1;
    static ArrayList<Integer>[] list;
    static int[] store;
    static boolean[] visited;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        n = Integer.parseInt(br.readLine());
        list = new ArrayList[n];
        store = new int[n];
        visited = new boolean[n];
 
        for(int i = 0; i < n; i++) {            
            list[i] = new ArrayList<Integer>();
        }
        
        for(int i = 0; i < n-1; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken())-1;    // 인덱스 맞추기 위함
            int y = Integer.parseInt(st.nextToken())-1;
            // 양방향
            list[x].add(y);
            list[y].add(x);
        }
        
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            store[i] = Integer.parseInt(st.nextToken())-1;
        }    
        
        dfs(0);
        System.out.println(result);
    }
 
    static void dfs(int x) {
        visited[x] = true;
        HashSet<Integer> set = new HashSet<>();    // 중복이 없는 set
        for(int next : list[x]) {
            if(!visited[next]) {
                set.add(next);    // x의 자식 노드들 저장
            }
        }
        // 자식이 없는 노드라면 끝내기
        if(set.size() == 0) {
            return;
        }
        if(set.contains(store[idx])) {    // 노드의 다음에 올 수 있는 후보 중 하나(즉, 자식 노드 중 하나)라면
            dfs(store[idx++]);            // 계속 진행
        }else {
            result = 0;
            return;
        }
    }
}
 

 

 

 

---

자식 노드를 어떻게 저장할까 고민이 많았는데.. contains를 쓰는 방법이 있을 줄이야