https://www.acmicpc.net/problem/16920
16920번: 확장 게임
구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위
www.acmicpc.net
탐색 종료 조건 부분에서 고생했던 문제였다. 처음에는 지도를 입력받을 때 빈칸의 개수를 세어놓고 빈칸이 0이 될 때까지 플레이어 순서대로 경로탐색을 수행하는 방법으로 시도했으나, 벽으로 둘러싸인 빈 공간의 가능성을 뒤늦게 깨달았다.
풀이
각 플레이어에게 해당하는 경로탐색용 큐 Array(repeating: [[Int]](), count: p+1)를 생성하여 앞으로 방문해야할 공간의 좌표를 담아둔다. 이후 모든 플레이어의 큐가 비어있는 상태가 될 때까지 각 플레이어 턴마다 Si번 경로탐색을 수행하면 된다. 큐의 첫 수행 좌표는 지도를 입력받을 때 큐에 담아두면 된다.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [1388] 바닥 장식 (0) | 2022.10.31 |
|---|---|
| [1063] 킹 (1) | 2022.10.28 |
| [9328] 열쇠 (0) | 2022.10.25 |
| [2011] 암호코드 (0) | 2022.10.24 |
| [11967] 불켜기 (0) | 2022.10.19 |