https://www.acmicpc.net/problem/16940
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main{
static int n;
static boolean[] visit;
static ArrayList<ArrayList<Integer>> list;
static int[] expect;
static int[] parent;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
list = new ArrayList<>();
visit = new boolean[n+1];
expect = new int[n+1];
parent = new int[n+1];
for(int i=0; i<=n; i++){
list.add(new ArrayList<>());
}
for(int i=1; i<n; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
list.get(a).add(b);
list.get(b).add(a);
}
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=1; i<=n; i++){
expect[i] = Integer.parseInt(st.nextToken());
}
bfs();
}
public static void bfs(){
Queue<Integer> q = new LinkedList<>();
q.add(1);
visit[1] = true;
if(expect[1]!= 1){ // 첫번째 원소가 1이 아니라면
System.out.println(0);
System.exit(0);
}
int idx = 2;
while(!q.isEmpty()){
int cur = q.poll();
int cnt=0;
for(int next: list.get(cur)){ // cur의 자식 노드들을 탐색하며 부모 배열에 저장
if(!visit[next]){
visit[next] = true;
parent[next] = cur; // next의 부모는 cur
cnt++;
}
}
for(int i=0; i<cnt; i++){
int expectNum = expect[idx++];
if(parent[expectNum] != cur){ // 부모가 cur이 아니라면 종료
System.out.println(0);
System.exit(0);
}
q.add(expectNum);
}
}
System.out.println(1);
}
}
입력에 나와있는대로 자식 노드들을 큐에 넣기 전에 이 노드들의 부모가 맞는 부모인지 체크하는 과정이 필요하다.
맞는 부모라면 큐에 그 자식들을 집어넣고, 아니면 종료한다.
'ALGORITHM' 카테고리의 다른 글
[JAVA] 백준 2146 - 다리 만들기 (0) | 2022.12.23 |
---|---|
[JAVA] 백준 16964 - DFS 스페셜 저지 (0) | 2022.12.23 |
[JAVA] 백준 16947 - 서울 지하철 2호선 (0) | 2022.12.19 |
[JAVA] 프로그래머스 - 비밀 지도 (0) | 2022.12.19 |
[JAVA] 프로그래머스 - 숫자 문자열과 영단어 (0) | 2022.12.19 |