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

문제 링크: https://www.acmicpc.net/problem/16964

16964번: DFS 스페셜 저지

1. 주의할 점

- 자식이 많은 부모의 경우, Leaf를 찍고 돌아왔을 때 다음 Node가 자신의 자식인지 어떻게 판별할 것인가?

- 브루트포스는 절대로 하지 않는다 (하면 안되는거 알잖아요..)

- TLE를 어떤 방식으로 해결할 것인가?

 

2. 구현

- 제목 그대로 DFS로 접근한다

- 모든 간선에 대한 정보는 Li[] 리스트 배열에 담는다

- Arr[] 배열을 통해 입력받은 노드 방문 순서를 담는다

- 전역변수 Idx를 설정하여 현재 방문해야 하는 노드(Arr[Idx])를 공유한다

- Set을 이용하여 해당 부모가 가지고 있는 자식들의 Node를 저장하고 Contains를 통해 자식 Node에 현재 찾고자 하는 Node가 있는지 확인한다.

- 현재 Node(curNode)가 Leaf라면 return을 하고 아니라면 자식중에 방문하지 않았고, 방문해야 하는 Node인 Val이 있는지 확인한다

- Val이 있다면 선처리 조건들을 수행하고 DFS를 계속한다

- Val이 없다면 While문을 중간에 빠져나오며, 결과적으로는 Idx==Num이 되지 못한다 

// 73% TLE
import java.io.*;
import java.util.*;

public class DFS_스페셜_저지 {

	static int num,answer;
	static List<Integer> li[];
	static boolean check[];
	static int arr[];
	static int idx;

	static void dfs(int curNode) {
		for(int i=0;i<li[curNode].size();i++) {
			int next = li[curNode].get(i);
			if(!check[next] && arr[idx]==next) {
				idx++;
				check[next]=true;
				dfs(next);
				i = -1;
			}
		}
	}

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		num = Integer.parseInt(br.readLine());

		//초기화
		li = new List[num+1];
		for(int i=1;i<=num;i++)
			li[i] = new ArrayList<>();
		arr = new int[num];
		check = new boolean[num+1];

		for(int i=0;i<num-1;i++) {
			String str = br.readLine();
			StringTokenizer st = new StringTokenizer(str);
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			li[a].add(b);
			li[b].add(a);
		}
		String str = br.readLine();
		StringTokenizer st = new StringTokenizer(str);
		for(int i=0;i<num;i++)
			arr[i] = Integer.parseInt(st.nextToken());

		if(arr[0]==1) {
			check[1]=true;
			idx=1;
			dfs(1);
		}

		System.out.println(idx==num ? 1 : 0);
	}
}

//AC
import java.io.*;
import java.util.*;

public class Main {

	static int num,answer;
	static List<Integer> li[];
	static boolean check[];
	static int arr[];
	static int idx;

	static void dfs(int par, int curNode) {
	    Set<Integer> s = new HashSet<>();
		for(int i=0;i<li[curNode].size();i++) {
			int next = li[curNode].get(i);
			if(next!=par) s.add(next);
		}
	    int len = s.size();
	    if(len==0) return;
		while(len>0){
		    int val = arr[idx];
		    if(!check[val] && s.contains(val)){
		        idx++;
		        check[val]=true;
		        dfs(curNode, val);
		        len--;
		    }
		    else break;
		}
	}

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		num = Integer.parseInt(br.readLine());

		//초기화
		li = new List[num+1];
		for(int i=1;i<=num;i++)
			li[i] = new ArrayList<>();
		arr = new int[num];
		check = new boolean[num+1];

		for(int i=0;i<num-1;i++) {
			String str = br.readLine();
			StringTokenizer st = new StringTokenizer(str);
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			li[a].add(b);
			li[b].add(a);
		}
		String str = br.readLine();
		StringTokenizer st = new StringTokenizer(str);
		for(int i=0;i<num;i++)
			arr[i] = Integer.parseInt(st.nextToken());

		if(arr[0]==1) {
			check[1]=true;
			idx=1;
			dfs(-1,1);
		}
		System.out.println(idx==num ? 1 : 0);
	}
}