[BOJ 28291] 레드스톤
- 문제풀이
문제
마인크래프트 고수인 당신은 midori, changwook987과 함께 마인크래프트를 플레이 중이다.
changwook987은 레드스톤 회로 블록들을 이용해 $W×H$ 크기의 사각형 맵에 회로를 만들었다. 회로 블록에는 레드스톤 가루, 레드스톤 블록, 레드스톤 램프가 있다.
- 레드스톤 가루(redstone_dust)는 상하좌우로 인접한 회로 블록에 매초마다 전기 신호를 전달하며, 전달할 회로 블록에 더 큰 전기 신호가 있다면 전달하지 않는다.
- 레드스톤 블록(redstone_block)은 전기 신호를 15만큼 가지고 있으며 상하좌우로 인접한 회로 블록에 15만큼의 전기 신호를 매초마다 전달한다.
- 레드스톤 램프(redstone_lamp)는 1 이상의 전기 신호를 받을 경우 불이 켜진다.
전기 신호는 회로 블록들이 작동하기 위해 필요한 에너지로 레드스톤 가루(redstone_dust)에서 다른 블록으로 전달될 때 1 감소하며 0 이하가 될 시 사라진다. 또한 여러 전기 신호가 한 블록에 모일 경우 그중 가장 큰 신호가 그 블록의 신호의 세기가 된다.
모든 회로 블록은 여러 번 행동할 수 있으며, 모두 동시에 행동한다.
changwook987은 midori에게 이 회로에 있는 모든 레드스톤 램프가 켜지는 순간이 있는지 알아보는 프로그램을 만들어 달라고 한다.
마인크래프트 초보인 midori는 당신에게 도움을 요청했다. midori를 도와 프로그램을 작성해 주자.
입력
첫째 줄에는 맵의 가로 길이 $W$와 세로 길이 $H$가 정수로 주어진다. $(1 \le W,H \le 50)$
둘째 줄에는 회로 블록의 개수 $N$이 정수로 주어진다. $(1 \le N \le W×H)$
셋째 줄부터 $N$개의 줄에는 회로 블록의 타입 $B$ ("redstone_dust", "redstone_block", "redstone_lamp" 중 하나)와 회로 블록의 가로 위치 $X$, 세로 위치 $Y$가 정수로 주어진다. $(0 \le X \le W-1; 0 \le Y \le H-1)$
또한 입력으로 주어지는 회로 블록에는 "redstone_lamp"가 하나 이상 포함되어 있다.
출력
모든 레드스톤 램프가 켜지는 순간이 존재하면 "success", 모든 레드스톤 램프가 켜지는 순간이 존재하지 않는다면 "failed"를 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 1sec | 1024MB |
풀이
마인크래프트의 레드스톤 회로 메커니즘을 격자판 위에서 시뮬레이션하여 모든 램프가 켜지는지 확인하는 문제다. 전기 신호가 상하좌우로 전달되면서 세기가 $1$씩 감소하고, 여러 신호가 한 블록에 모일 경우 그중 가장 큰 신호가 해당 블록의 세기가 된다는 점이 핵심이다. 이를 효율적으로 처리하기 위해 BFS 탐색을 활용한다.
해결 과정은 다음과 같다:
- 격자 데이터 구조화: $W \times H$ 크기의 격자에 레드스톤 가루(
DUST), 블록(BLOCK), 램프(LAMP)의 위치를 저장한다. - 멀티 소스 BFS 초기화: 모든 레드스톤 블록은 신호의 시작점이다. 모든 블록의 위치를 큐에 삽입하고, 해당 칸의 신호 세기를 $16$으로 설정한다. 이는 인접한 칸에 $15$의 신호를 전달하기 위한 처리다.
- 신호 전파 로직: 큐에서 현재 위치와 신호 세기를 꺼내 상하좌우 인접한 칸을 탐색한다.
- 전파 조건: 이동하려는 칸이 가루나 램프이고 아직 신호를 받지 않은 경우(
NONE)에만 새로운 신호 세기를 기록하고 큐에 삽입한다. 신호 세기가 $1$ 미만이 되면 더 이상 전파할 수 없으며, 램프는 신호를 받기만 하고 전달하지 않으므로 램프 도달 시 탐색을 중단한다. - 최종 판정: 모든 전파가 완료된 후 격자를 순회하며 모든 램프 위치의 신호 세기가 $0$보다 큰지 확인한다. 하나라도 켜지지 않은 램프가 있다면
failed, 모두 켜졌다면success를 출력한다.
격자의 최대 크기는 $50 \times 50$으로 총 $2\,500$개의 칸이 존재한다. 모든 칸을 최대 한 번씩 방문하여 탐색하므로 전체 시간 복잡도는 $O(WH)$이며, 이는 제한 시간 $1$초 내에 매우 여유롭게 수행 가능하다.
소스코드
Github Link : Source Code
참고 알고리즘 : BFS 탐색