네트워크 강의를 듣다가 이런 말이 있었다.
'네트워크 계층을 알고싶으면 헤더를 뜯어라'
헤더에 네트워크 계층에서 작동하기 위한 내용이 들어가있으니
그 헤더의 내용이 왜 들어있는지 알면 계층을 알 수 있다는 것이다.
이번 문제도 비슷한 맥락이다.
알고리즘을 어떻게 채점하는지 알면, 그 알고리즘의 작동방식에 대해 이해할 수 있다는 것이다.
BFS 스페셜 저지 성공
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 512 MB 11028 3012 1871 24.957%
문제
BOJ에서 정답이 여러가지인 경우에는 스페셜 저지를 사용한다. 스페셜 저지는 유저가 출력한 답을 검증하는 코드를 통해서 정답 유무를 결정하는 방식이다. 오늘은 스페셜 저지 코드를 하나 만들어보려고 한다.
정점의 개수가 N이고, 정점에 1부터 N까지 번호가 매겨져있는 양방향 그래프가 있을 때, BFS 알고리즘은 다음과 같은 형태로 이루어져 있다.
큐에 시작 정점을 넣는다. 이 문제에서 시작 정점은 1이다. 1을 방문했다고 처리한다.
큐가 비어 있지 않은 동안 다음을 반복한다.
큐에 들어있는 첫 정점을 큐에서 꺼낸다. 이 정점을 x라고 하자.
x와 연결되어 있으면, 아직 방문하지 않은 정점 y를 모두 큐에 넣는다. 모든 y를 방문했다고 처리한다.
2-2 단계에서 방문하지 않은 정점을 방문하는 순서는 중요하지 않다. 따라서, BFS의 결과는 여러가지가 나올 수 있다.
트리가 주어졌을 때, 올바른 BFS 방문 순서인지 구해보자.
입력
첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 BFS 방문 순서가 주어진다. BFS 방문 순서는 항상 N개의 정수로 이루어져 있으며, 1부터 N까지 자연수가 한 번씩 등장한다.
출력
입력으로 주어진 BFS 방문 순서가 올바른 순서면 1, 아니면 0을 출력한다.
간단한 문제이다.
BFS 채점용 코드를 만들어라는 것이다.
BFS의 정점을 Que에 넣을때, 정렬되지 않은 상태로 들어갈 수 있으니
BFS 탐색이 맞냐, 아니냐만 채크하면 되는 것이다.
내 문제풀이는 다음과 같다.
- 각 정점의 자식노드를 찾는다.
- 슬라이싱하며 자식노드별로 있는지 확인한다.
즉, 한 정점이 들어오면 그 자식노드들이 묶음으로 들어와야 한다는 소리다.
예를들어보면
Node 1의 자식 = [2,3,4]
Node 2의 자식 = [2-1,2-2]
Node 3의 자식 = [3-1,3-2]
Node 4의 자식 = [4-1,4-2]
위의 노드가 있을때
[1,2,3,4,2-1,2-2,3-1,3-2,4-1,4-2]
[1,3,2,4,3-1,3-2,2-1,2-2,4-1,4-2]
[1,2,4,3,2-1,2-2,4-1,4-2,3-1,3-2]
...
위와 같이 한 노드의 자식이 세트로 와야 한다는 의미이다.
[1,2,3,4] 순서로 들어온다면
1을 탐색했을때 Que에는 [2,3,4]가 들어가고
2를 탐색했으니 [2-1,2-2]는 한묶음으로 들어가야된다는 뜻이다.
간단하게 적었지만 BFS를 관통하는 핵심적인 내용이라고 생각했다.
