[BOJ 23887] 백준 23887번 - 프린트 전달
| GBS Coding Contest 2021 풀이 | ||
|---|---|---|
| A | [BOJ 23885] 비숍 투어 | |
| B | [BOJ 23886] 알프수 | |
| C | [BOJ 23887] 프린트 전달 | |
| D | [BOJ 23888] 등차수열과 쿼리 | |
| E | [BOJ 23889] 돌 굴러가유 | |
| F | [BOJ 23890] 달팽이팽이 | |
| G | [BOJ 23891] 타이어 끌기 | |
| H | [BOJ 23892] 바코드 찢기 |
1. 문제
$23887$. 프린트 전달 (GBS Coding Contest 2021 Open C번)
2. 풀이
크게 두 가지 과정으로 나누어 볼 수 있다. 첫 번째로는 프린트를 전달하는 경로를 알아내야 하고, 두 번째로는 각 학생이 받아야 하는 프린트의 수를 구해야 한다.
프린트는 현재 프린트를 갖고 있는 학생 모두가 동시에 자신의 주변 모두에게 주는 방식으로 전달된다. 따라서 프린트를 처음 받은 사람들을 전부 처리하고, 프린트를 두번째로 받은 사람들을 전부 처리하는 방식으로 진행되어야 하므로, BFS를 생각할 수 있다.
이때, $3$번 조건에 의해 여러 명에게 받는다면 번호가 가장 작은 학생에게 받아야 하므로, BFS로 이미 방문한 학생이라도 그 학생이 어떤 학생에게 프린트를 받았는지를 체크하여 수를 비교하는 작업이 필요하다. 따라서 이를 저장해주는 배열이 추가로 필요하다. (나는 이를 코드에서 Prev 배열로 두었다.)
BFS로 노드들을 방문하면서 해당 노드의 이전 노드 값도 동시에 채워준다. 이때 동일 단계에서 이미 방문한 노드라면, 그 노드의 저장된 이전 노드 값과 지금 이전 노드 값을 비교하여 최솟값으로 갱신한다. 이때, ‘동일 단계’라는 의미는 작업이 동시에 진행되는 어떤 순간을 의미한다.
프린트를 두번째로 받은 사람들이 프린트를 나눠주는 순간과 프린트를 세번째로 받은 사람들이 프린트를 나눠주는 순간은 서로 다른 단계이다. 따라서 BFS를 돌릴 때, 그 노드의 visited 값을 확인하여 동일 단계인지 확인하는 작업이 필요하다. ($2$단계에서 프린트를 받은 노드를 $3$단계에서 방문하려고 하는 것은 옳지 않다는 의미이다.) (코드 42줄)
어떤 노드의 이전 노드 값이 Prev에 전부 저장되었으므로 이 정보를 이용하여 전체 노드를 탐색할 수 있다. 이때, 조건 상으로 한 학생이 두 명 이상의 학생에게 프린트를 받을 수 없으므로 어떤 노드의 Prev 노드 값은 단 하나만 존재한다.
순방향으로 탐색하면 끝 노드에 도달해야 결과를 정리할 수 있어서 계산이 어렵다. 대신 역방향으로 탐색하면 처음 노드 값을 $1$로 설정하며 어떤 노드에 도달과 동시에 계산을 끝마칠 수 있어서 쉽다. 따라서 역방향 탐색을 선택한다.
Prev[a]=b를 a=Next[b]로 간주할 수 있다. 단, 어떤 노드의 Prev 노드 값이 존재하지 않는 경우는 그 노드가 탐색이 불가능하다는 의미이므로 프린트를 받을 수 없어 $-1$을 출력하고 종료한다.
- 어떤 노드로부터 다른 노드로 뻗어 나가는 단방향 경로는 하나이다.
- 어떤 노드로 들어오는 단방향 경로는 여러 개이다.
- 들어오는 노드들의 총합이 계산된 후, 그 값을 다음 노드로 전달한다. 즉, 들어오는 노드들이 전부 계산된 후에 다음 노드로 뻗어 나가야 한다.
이러한 조건들을 살펴보면, 이전 과정을 전부 처리한 후 다음 일을 수행하는 Topology Sort(위상정렬) 방식으로 탐색하는 것이 적절하다는 것을 알 수 있다.
Indegree(해당 노드로 들어오는 경로의 개수)가 $0$인 노드들부터 프린트 $1$장으로 시작, 뻗어 나가면서 도착 노드에 값을 누적시켜주는 방식으로 탐색하여 모든 각각의 학생이 받아야 하는 프린트의 수를 구할 수 있다.
3. 채점 결과
4. 회고
.
댓글남기기