bfs 스페셜 저지
-
백준 16940번 BFS 스페셜 저지PS 2020. 4. 8. 20:56
https://www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net 그래프가 주어지고 bfs를 돌렸을 때, 나올 수 있는 방문 순서인가를 묻는 문제입니다. 방문 깊이?뿐만 아니라 큐에 들어간 순서를 고려해야 합니다. A-a B-b A, B가 동일 depth이고 a,b가 동일 depth일 때, A가 먼저 큐에 들어갔으면 A, B, a, b가 방문 순서가 되겠지요. q.front()의 결과로 나온 노드의 자식노드가 전부 나왔는가를 확인합니다. 이의 결과로 두 가지가 있습니다. 1. 만약 자식노드가 전부 나왔다. 이 경우는 자식노드를 큐에 넣어주는 순서를 입력받은 순서대로 하여 넣어줍..