# (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만큼 추가한다는 것이다!

```java
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);
	}

}

```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://heunnajo.gitbook.io/algorithms-problem-solving-skills/graph/challenge-bfs-special-judge.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.