백준 16940번. BFS 스페셜 저지 (Java, Kotlin)

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

간단해보였는데 굉장히 많은 시도를 한 문제입니다.

처음에는 연결된 노드 갯수를 기준으로 하였고, 그 다음에는 depth를 기준으로 하였습니다.

그러나 이 문제의 핵심은 결국 어떤 정점은

1) 자신의 부모 정점이 무엇인가

2) 자신의 자식 정점은 몇개가 있는가

위 값들을 전부 아는 상태로 시작해야 합니다.

우선 처음엔 BFS 를 돌면서 부모 노드와 자식 노드의 갯수를 전부 기록해 둡니다.

그리고 주어진 순서를 쭉 순회하면서 현재 노드가 기록했던 부모 노드와 일치하는지 비교하면 됩니다.

parentQueue 라는 변수를 사용하였는데, 부모 노드만을 집어넣는 전용 큐입니다.

childSize 라는 자식 노드의 갯수가 1 이상인 노드들은 전부 parentQueue에 저장되며 자식 노드가 전부 나온 후에야 큐에서 빠져나옵니다.

만약 연속해서 나오는 자식 노드의 갯수가 저장된 childSize와 일치하지 않는다면 불가능한 BFS 라는 뜻이 되겠죠.