[BOJ 24513] 백준 24513번 - 좀비 바이러스
1. 문제
$24513$. 좀비 바이러스 (2022 ICPC Sinchon Winter Algorithm Camp Contest E번)
2. 풀이
$1$과 $2$를 시작점으로 정해서 BFS를 돌리며 탐색하는 문제이다. 단, $1$과 $2$ 바이러스가 같은 시간대에 동시에 퍼진 마을을 구분하는 작업이 필요하다. 각 마을을 방문한 시각을 저장하는 배열을 만들어서, BFS를 돌리면서 동시간대에 $1$과 $2$ 바이러스가 동시에 퍼졌는지를 체크해주는 방법이 있다.
하지만 이 방법대로 구현하면, 동시간대의 바이러스 확산을 처리할 때마다 전체 맵을 탐색해서 방문 시간을 체크해야 한다. 맵의 최대 크기는 $1,000,000$이기 때문에 오버헤드가 크다. 따라서 방문과 동시에 시간을 체크하는 방식의 구현이 필요하다.
$1$ 바이러스가 퍼진 곳은 방문 시간을 홀수, $2$바이러스가 퍼진 곳은 방문 시간을 짝수로 구분한다. 각 시간대별 처리가 모두 끝나면, 방문 시간을 $+2$씩 해주는 방식이다. 즉, $1시간대=1,2$ / $2시간대=3,4$ / $3시간대=4,5$ / $4시간대=5,6$ 이렇게 나뉜다.
- queue에 $1$도시, $2$도시를 차례로 push 한다.
- queue에서 하나를 pop하여 네 방향의 마을을 조사한다.
- 범위를 벗어나거나 치료제를 가진 마을이거나 $3$ 바이러스가 퍼진 곳이면 방문 X
- 이미 동시간대에 자기 바이러스가 방문한 곳이면 방문 X -> 자기 바이러스 종류와 시간대를 통해 체크 가능
- 이미 동시간대에 다른 바이러스가 방문한 곳이면 $3$ 바이러스로 만듦 -> 자기 바이러스 종류와 시간대를 통해 체크 가능
- 위의 모든 경우가 아닌 경우 -> 바이러스 시간대를 체크하고 queue에 push
- 바이러스의 종류가 $2$에서 $1$로 변하는 때가 한 시간대가 종료된 것이다. 그 경우, 시간대 구분을 위해 변수에 $+2$를 해준다.
$2$에서 queue에서 하나를 pop하는 과정에서 해당 마을이 $3$ 바이러스가 퍼진 곳이면 작업 수행을 하지 않아야 한다. $3$ 바이러스가 퍼진 곳은 queue에 넣지 않았으므로 해당 작업이 필요하지 않다는 생각을 할 수 있지만 아니다.
$3$ 바이러스를 구분하는 시점은 짝수시간 바이러스가 퍼질 때이다. 이를 구분할 수 없는 홀수시간 바이러스가 퍼질 때는 가능한 모든 곳이 queue에 push된다. 따라서, 짝수시간 바이러스가 $3$ 바이러스가 퍼진 곳을 알아냈다면, 그곳은 홀수시간 바이러스가 퍼질 때 이미 queue에 push된 후이다.
따라서 이를 queue에서 제거해야 하는데 너무 오버헤드가 크므로, 단순히 꺼냈을 때 $3$ 바이러스가 퍼진 곳인지 확인하여 해당 마을을 그냥 지나가게 만든다.
3. 채점 결과
4. 회고
$1$ 바이러스를 전부 탐색 후, $2$ 바이러스를 탐색하는 순서로 진행되게 구현했는데, 처음 queue에 집어넣을 때 $2$ 바이러스$\rightarrow$ $1$ 바이러스 순서로 queue에 push되는 경우가 생겨버리게 구현해버려서 WA를 받았다.
댓글남기기