[오늘의 문제]
https://www.acmicpc.net/problem/16920
[오늘의 학습 키워드]
- 그래프 탐색
- 그래프 이론
- 너비 우선 탐색, BFS
- 구현
1. 문제설명
격자판 위에 플레이어의 번호와 동일한 성이 존재합니다.
각 플레이어 별로 움직일 수 있는 범위 S가 주어질 때, 1번 플레이어 부터 9번 플레이어 까지 순서대로 자신의 성을 확장합니다.
예를들어 1번 플레이어는 성이 0, 0 위치에 존재하고 2칸의 범위를 움직일 수 있습니다.
2번 플레이어는 3, 3에 성이 존재하고 1칸의 범위를 움직일 수 있습니다.
1턴 움직이면
각 플레이어의 성이 이렇게 확장 됩니다.
다음턴에는
이렇게 확장되어 1번 플레이어가 총 13칸을 차지하고 2번 플레이어는 3칸을 차지하게 됩니다.
이렇게 동작하도록 코드를 작성해야 합니다.
[제한사항]
- 시간 제한 2초
- 메모리 제한 512MB
- 1 ≤ N, M ≤ 1,000
- 1 ≤ P ≤ 9
- 1 ≤ Si ≤ 10^9
2. 접근방식
각 플레이어는 이동 순서가 정해져 있습니다.
1번 플레이어부터 최대 9번 플레이어 까지 순서대로 자신의 성을 확장시켜 나갑니다.
그렇기에 앞선 예시 그림처럼 불합리한 칸의 차지가 이루어 질 수 있는 것이죠
이를 구현하기 위해서는 각 플레이어별로 queue를 만들어 주고 해당 플레이어의 이동 범위에 따라 4방향으로 성을 확장시켜 준 뒤
다음 플레이어로 순서가 넘어가야 합니다.
코드로 자세히 설명해 보겠습니다.
3. 코드
import sys
input = sys.stdin.readline
from collections import deque
# 입력
N, M, P = map(int, input().split())
S = [0] + list(map(int, input().split()))
board = [list(map(str, input().strip())) for _ in range(N)]
# 플레이어별로 queue 생성
queues = [deque() for _ in range(P + 1)]
answer = [0] * (P + 1)
# 초기 성 위치 찾고 저장
for i in range(N):
for j in range(M):
if board[i][j] != '.' and board[i][j] != '#':
player_num = int(board[i][j])
queues[player_num].append((i, j))
answer[player_num] += 1
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
while True:
moved = False
for p in range(1, P + 1):
# 플레이어의 queue 가져오기
queue = queues[p]
step = S[p]
# 없다면 해당 플레이어 건너 뛰기
if not queue:
continue
# 플레이어가 이동 가능한 범위만큼 반복
for _ in range(step):
next_queue = deque()
while queue:
x, y = queue.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if 0 <= nx < N and 0 <= ny < M and board[nx][ny] == '.':
board[nx][ny] = str(p)
answer[p] += 1
next_queue.append((nx, ny))
moved = True
# queue 이동을 완료했는데 next_queue가 없다면 해당 플레이어 종료
if not next_queue:
break
# 있다면 queue에 덮어쓰기
queue.extend(next_queue)
# 모든 이동이 완료된 경우 while 종료
if not moved:
break
print(*answer[1:])[코드설명]
# 입력
N, M, P = map(int, input().split())
S = [0] + list(map(int, input().split()))
board = [list(map(str, input().strip())) for _ in range(N)]
# 플레이어별로 queue 생성
queues = [deque() for _ in range(P + 1)]
answer = [0] * (P + 1)
# 초기 성 위치 찾고 저장
for i in range(N):
for j in range(M):
if board[i][j] != '.' and board[i][j] != '#':
player_num = int(board[i][j])
queues[player_num].append((i, j))
answer[player_num] += 1
우선 각 플레이어 별로 queue가 존재해야 하기 때문에 플레이어의 갯수에 맞춰 queues 라는 배열에 deque를 플레이어 수만큼
생성해 줍니다.
중첩 반복문을 이용해 플레이어 번호에 맞춰 해당 플레이어의 queue에 초기 위치를 저장해 주고 해당 플레이어가 차지한 칸의 크기를 번호에 맞춰 저장해 줍니다.
이러면 queues 배열은 여러개의 deque가 저장된 상태가 됩니다.
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
while True:
moved = False
for p in range(1, P + 1):
# 플레이어의 queue 가져오기
queue = queues[p]
step = S[p]
# 없다면 해당 플레이어 건너 뛰기
if not queue:
continue
각 플레이어 별로 돌아가며 성을 확장시켜야 합니다.
플레이어 번호는 1번부터 최대 9번까지 존재하기에 반복문의 범위를 1 부터 P + 1 까지 지정하였고 해당 플레이어의 queue와 이동 범위를 가져옵니다.
또한 board에서 더이상 성이 확장될 수 없을 때까지 계속 반복되어야 하기에 while을 True로 설정하여 무한 반복으로 설정해주고 플래그 moved를 설정해 주었습니다.
각 플레이어 별로 queue 에 성의 이동 정보를 저장하는데 만약 queue가 비었다면 더이상 해당 플레이어는 이동할 수 없다는 의미이니 continue를 이용해 차례를 뛰어넘어 줍니다.
# 플레이어가 이동 가능한 범위만큼 반복
for _ in range(step):
next_queue = deque()
while queue:
x, y = queue.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if 0 <= nx < N and 0 <= ny < M and board[nx][ny] == '.':
board[nx][ny] = str(p)
answer[p] += 1
next_queue.append((nx, ny))
moved = True
# queue 이동을 완료했는데 next_queue가 없다면 해당 플레이어 종료
if not next_queue:
break
# 있다면 queue에 덮어쓰기
queue.extend(next_queue)
# 모든 이동이 완료된 경우 while 종료
if not moved:
break
앞선 예시에서 플레이어의 이동범위가 2가 되면 성을 확장한 이후 다시한번 더 성을 확장할 수 있습니다.
그때의 범위는 성의 위치를 기준으로 4방향이죠
그말은 최초 queue를 동작하여 모든 queue를 한번 비워주고 새롭게 저장된 위치를 다른 queue에 저장했다가 저장된 위치에서 다시한번 BFS 탐색이 이루어져야 하죠
이 동작은 플레이어의 이동범위 즉, step 만큼 이루어져야 합니다.
따라서 가장 먼저 플레이어의 이동 범위를 설정해주고 queue를 비웠다가 새롭게 저장하기 위해서 next_queue를 생성해 주었습니다.
이후 동일하게 BFS 탐색을 실시하며 board에 플레이어의 성을 기록해 주고, 다음 이동 범위를 next_queue에 저장해 줍니다.
이때 동일하게 플레이어의 확장된 성의 갯수를 answer의 플레이어 번호에 맞춰 저장해 줍니다.
다음 이동범위는 next_queue에 저장하여 모든 queue를 한번 비울 수 있도록 해주었습니다.
이때 next_queue를 생성하였는데 next_queue에 저장된 이동 정보가 없다면 해당 플레이어가 몇 칸을 이동할 수 있던 더이상 이동이 불가능하기 때문에 break로 해당 플레이어의 이동을 종료해주었고
그렇지 않다면 next_queue의 정보를 queue에 저장하기 위해 extend를 사용해 주었습니다.
extend는 리스트의 전체 정보를 queue에 새로운 queue에 저장할 때 사용합니다.
만약 앞쪽에 넣고 싶다면 extendleft를 사용해 주면 됩니다.
전체 플레이어의 동작이 종료 되었는데 만약 moved가 False라면 BFS 탐색 과정이 발생하지 않은 것입니다.
그 말은 모든 플레이어의 성이 board 위에서 동작을 완료하였기 때문에 더이상 이동할 곳이 없다는 의미이죠
그때 while문을 종료해 주었습니다.
결과를 출력할 때는 각 플레이어가 차지한 칸의 갯수를 출력해 주어야 하니 플레이어의 번호에 맞춰 1번부터 각 플레이어가 차지한 칸의 갯수를 출력해 주었습니다.
4. 결과
[회고]
이번 문제는 시간초과와의 싸움 이었습니다.
기존에 작성한 코드는 하나의 queue를 이용하여 각 플레이어의 이동 순서를 보장하려 하였는데 그렇게 하면 문제가 있었습니다.
플레이어의 이동 범위가 2칸 이상인 경우 플레이어가 1칸 이동하고 그 다음칸 이동을 위해서 queue의 뒤에 이동 정보를 저장하게 되는데
이때 플레이어의 순서가 꼬이게 되었습니다. 이를 해결하려고 순서가 보장되는 queue인 heapq도 생각하였는데
그러면 매번 queue의 순서가 정렬되어 영원히 2번 플레이어의 차례가 오지 않게 되었습니다.
결국 제대로된 동작을 하기 위해서는 각 플레이어 별로 queue가 필요하였고 리스트에 플레이어의 번호에 맞춰 queue를 생성해 주었습니다.
그 다음에는 플레이어 별로 BFS 탐색을 실시하는데 next_queue를 만들고 정보를 queue에 저장하는 과정이 시간이 오래 걸려 최적화 하는데 시간이 많이 걸렸습니다.
결국 플레이어는 자신이 이동가능한 칸을 1턴에 모두 이동하여야 합니다.
이를 제대로 구현하려면 결국에는 2개의 queue가 필요한데 처음에는 생성한 next_queue에 정보를 저장하고 queue에 치환하는 과정에 시간이 오래 걸렸고 시간을 줄이는 방법을 찾다고 extend가 떠올랐습니다.
불필요한 동작들을 최적화 하기 위해서 next_queue에 이동 정보가 없다면 차례를 종료하는 코드를 추가하고,
queue에 이동정보가 없다면 동일하게 차례를 종료하는 코드들을 추가하며 최적화를 실시하였고 문제를 맞출 수 있었죠
조금 까다로운 문제긴 했는데 조건이 엄청 어렵진 않고 조금만 생각해보면 쉽게 해결이 가능한 문제 였어서 재밌게 푼 문제 였습니다.
'알고리즘' 카테고리의 다른 글
| [백준] 9328 열쇠 - 골드 (1) | 2025.06.14 |
|---|---|
| [백준]11967 불 켜기 - 골드 2 (0) | 2025.06.12 |
| [백준] 9466 텀 프로젝트 - 골드 (0) | 2025.06.10 |
| [백준] 5427 불 - 골드 4 (0) | 2025.06.09 |
| [백준] 1600 말이 되고픈 원숭이 - 골드 3 (1) | 2025.06.07 |