(Challenge)BFS Special Judge

2회차 풀이 틀린 이유

1. bfs 순서 입력받을 때 1을 빼주지 않아서 큐에 넣고 뺀 건(x) 0인데, order[0] = 1, x = 0으로 같지 않기 때문에 0이라는 오답을 출력했다.(사실은 제대로 잘 실행된 것임)

2. 큐가 비었을 때 0을 출력하고 프로그램을 종료해야한다.? 큐가 비었으면 프로그램을 종료하는 것까진 알겠는데 왜 0을 출력하나?

• 문제의 핵심

order의 순서가 x의 인접노드인지 확인하는 것을 구현하는 것이다! x의 인접노드를 바로 큐에 넣는 게 아니라, 인접노드들을 parent라는 배열에 저장하고, 인접노드 갯수를 세준다. 예를 들어 x=0, x의 인접노드가 1,2 2개일 때 parent[0]=1,parent[0]=2는 안 되지만, parent[1]=0,parent[2]=0 은 가능하기 때문에 x의 인접노드를 인덱스로 하는 parent 배열의 값으로 x를 넣어준다!

인접노드 갯수만큼 order 배열 값들을 큐에 넣어준다! 단, 큐에 넣을 때, parent[order 배열 값]이 x인지(x의 인접노드인지) 확인하고 넣어준다! 맞으면 큐에 넣고, 아니면 순서가 틀린 것이므로 0을 출력하고 프로그램 종료!

• m이 존재하는 이유, 의미

m은 1에서 시작한다. 단순히 큐의 크기를 의미하는 것이 아니라 큐에 넣을 수, order 배열의 인덱스가 된다! 왜냐하면 order[0]에서 시작하고, 이것의 인접노드는 order[1]부터 cnt(인접노드 갯수)만큼이기 때문에 1(m)부터 cnt만큼 큐에 넣고! m=1-> m+cnt=3 으로 업데이트해준다! m=3의 의미는 그 다음 정점의 인접노드 추가는 order[3]부터 cnt만큼 추가한다는 것이다!

import java.util.*;
public class BFS_SpecialJudge_2nd {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		ArrayList<Integer>[] a = new ArrayList[n];
		int[] parent = new  int[n];//n만큼 생성하는 게 맞나?
		boolean[] c = new boolean[n];
		int[] order = new int[n];
		for(int i=0;i<n;i++) {
			a[i] = new ArrayList<>();
		}
		for(int i=0;i<n-1;i++) {//간선정보 저장~
			int u = sc.nextInt()-1;
			int v = sc.nextInt()-1;
			a[u].add(v);a[v].add(u);
		}
		for(int i=0;i<n;i++) {
			order[i] = sc.nextInt()-1;
		}
		//인접노드를 돌면서 인접노드 관계를 나타내는 parent배열을 생성하고, 현재 정점 x의 인접노드 갯수를 세준다!
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(0);c[0] = true;
		int m=1;
		for(int i=0;i<n;i++) {//i는 0부터 정점 갯수만큼 반복한다. order[0]부터 order[n-1]까지.
			//Round1.큐에서 꺼낸 x(0)와 order[0] 비교.
			//Round2.x(0)의 인접노드를 큐에 넣었기 때문에
			//		x(0)의 인접노드와 order[1]과 비교. - x의 인접노드 : 1,2 이고 order:0 1 2 3 또는 0 2 1 3일 때
			//parent[1] = 0, parent[2] = 0 1,2 둘다 parent 값이 x이므로(인접노드가 x) 만족~!
			//이러한 n개의 정점에 대해 order의 각 값과 비교 연산을 n개 만큼반복하기 때문에 for(i=0~n)돌려준다!
			if(q.isEmpty()) {//큐가 비면? bfs 다 돌았다는 뜻.근데 왜 0출력하고 종료하나?
				System.out.println(0);
				System.exit(0);
			}
			int x = q.remove();
			if(x != order[i]) {
				System.out.println(0);
				System.exit(0);
			}
			int cnt=0;
			for(int y:a[x]) {
				if(c[y]==false) {
					parent[y] = x;cnt++;//인접 노드 갯수 센다!
				}
			}
			for(int j=0;j<cnt;j++) {
				if(m+j>=n || parent[order[m+j]] != x) {
					System.out.println(0);
					System.exit(0);
				}
				q.add(order[m+j]);
				c[order[m+j]]=true;
			}
			m+=cnt;
		}
		System.out.println(1);
	}

}