[BOJ_Gold 2] 16920 - 확장게임 [python]

16920번: 확장 게임

문제

구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위에 있다. 한 칸 위에 성이 두 개 이상인 경우는 없다.

게임은 라운드로 이루어져 있고, 각 라운드마다 플레이어는 자기 턴이 돌아올 때마다 성을 확장해야 한다. 제일 먼저 플레이어 1이 확장을 하고, 그 다음 플레이어 2가 확장을 하고, 이런 식으로 라운드가 진행된다.

각 턴이 돌아왔을 때, 플레이어는 자신이 가지고 있는 성을 비어있는 칸으로 확장한다. 플레이어 i는 자신의 성이 있는 곳에서 Si칸 만큼 이동할 수 있는 모든 칸에 성을 동시에 만든다. 위, 왼쪽, 오른쪽, 아래로 인접한 칸으로만 이동할 수 있으며, 벽이나 다른 플레이어의 성이 있는 곳으로는 이동할 수 없다. 성을 다 건설한 이후엔 다음 플레이어가 턴을 갖는다.

모든 플레이어가 더 이상 확장을 할 수 없을 때 게임이 끝난다. 게임판의 초기 상태가 주어졌을 때, 최종 상태를 구해보자.

입력

첫째 줄에 격자판의 크기 N, M과 플레이어의 수 P가 주어진다. 둘째 줄에는 S1, S2, ...SP가 주어진다.

다음 N개의 줄에는 게임판의 상태가 주어진다. '.'는 빈 칸, '#'는 벽, '1', '2', ..., '9'는 각 플레이어의 성이다.

모든 플레이어는 적어도 하나의 성을 가지고 있으며, 게임에 참가하지 않는 플레이어의 성이 있는 경우는 없다.

출력

플레이어 1이 가진 성의 수, 2가 가진 성의 수, ..., P가 가진 성의 수를 공백으로 구분해 출력한다.

제한

• 1 ≤ N, M ≤ 1,000
• 1 ≤ P ≤ 9
• 1 ≤ Si ≤ $10^9$

---

크게 어렵지는 않은 문제입니다.

 

문제에서 주어진 규칙에 맞게 각 플레이어별로 순서대로 BFS를 진행하며 방문한 정점들에 대해

처리를 진행해주면 됩니다.

 

다만, 각 플레이어별로 성에서부터 정복이 가능한 칸을 나타내는 Si가 10^9까지 나올 수 있지만, 

실제로 모든 맵의 정복을 위해 필요한 가장 큰 Si는 $10^6$보다 작습니다. 때문에, 시간 초과를 막기 위해서는

큐에 더이상 방문 가능한 정점이 나와있는 경우 탐색을 종료해주는 조건문을 추가해 주어야합니다.

 

import sys

input = sys.stdin.readline
from typing import List
from collections import deque
n,m,players = map(int,input().split())
conquerPerTurn = [0] + list(map(int,input().split()))
board = [list(input().rstrip()) for _ in range(n)]
dx,dy = [1,0,-1,0],[0,1,0,-1]


areaPerPlayer = [0] * (players + 1)
queuePerPlayer = [deque() for _ in range(players+1)]
for i in range(n):
    for j in range(m):
        if not board[i][j].isdigit(): continue
        queuePerPlayer[int(board[i][j])].append((i,j))
        areaPerPlayer[int(board[i][j])] += 1


def bfs(playerCode: int, queue: deque) -> bool:  # update여부 리턴
    update = False
    for _ in range(conquerPerTurn[playerCode]):
        if not queue: break
        for _ in range(len(queue)):
            x,y = queue.popleft()

            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]
                if not(0 <= nx < n and 0 <= ny < m and board[nx][ny] == "."): continue    #정복 가능한 지역인 경우에만 확인
                queue.append((nx,ny))
                board[nx][ny] = playerCode
                areaPerPlayer[playerCode] += 1  #새로 정복한 지역만큼 칸 추가
                update = True
    return update

while True:
    update = False

    for i in range(1,players+1):    #모든 플레이어에 대해 탐색 진행
        if bfs(i,queuePerPlayer[i]):
            update = True
        #print(*board,sep="\n",end= "\n\n")

    if not update:
        print(*areaPerPlayer[1:])
        exit()

모든 정점에 대해 한번씩만 방문을 수행하므로, 전체적인 시간 복잡도는 $O(NM)$이라고 볼 수 있겠습니다.