[BOJ] 16920. 확장 게임 (🥇, BFS)

🔗

풀이

플레이어들이 순서대로 s만큼 확장해나간다. 확장이기 때문에 너비 우선 탐색을 사용했다. 플레이어들이 탐색을 시작할 수 있는 위치를 저장해뒀다가 각 턴마다 그 위치들에서 너비 우선 탐색을 통해 확장해나갔다. s만큼 확장하고 마지막에 저장된 위치들은 다음 턴에 탐색할 수 있도록 다시 저장했다.

확장은 더 이상 확장이 진행될 수 없을 때까지 이루어진다. 일반적으로 여기서 다들 더 이상 남은 칸이 없을 때까지라고 생각하고, 나도 그랬다. 그래서 . 칸이 남아있다면~ 으로 접근했지만 안타깝게도 시간초과에 걸렸다.

바로 이런 반례 때문이다.

1#........
#.........
2#.......#
3#......#4

벽에 가로막혀 더 이상 이동할 수 없어서 다 채울 수 없는 경우에도 무한으로 돌아가다보니 시간초과가 난 것이었다. 위의 반례는 아주 극단적인 예제인데 이런 경우말고 벽에 둘러싸인 .라던가 이런 게 하나라도 있는 경우에는 내가 건 종료조건으로는 종료될 수 없었다.

그래서 더 이상 탐색할 수 있는 위치가 없을 때 종료했다. 위에서 다음 턴마다 탐색하기 위해 탐색할 위치들을 저장한다고 했는데 이 위치들이 모든 플레이어에게 단 하나도 남아있지 않을 때 종료하는 조건이다.

import sys
input = sys.stdin.readline
from collections import defaultdict

def is_finish():
    return sum(list(castle.values())) != total\
            and any(list(player.values()))

def bfs(queue, p, s):
    global castle
    while queue and s:
        new_queue = []
        for r, c in queue:
            for dr, dc in dirs:
                nr, nc = r+dr, c+dc 
                if 0<=nr<N and 0<=nc<M and board[nr][nc] == '.' and board[nr][nc] != '#':
                    board[nr][nc] = p 
                    new_queue.append((nr, nc))
        queue = new_queue[:]
        castle[p] += len(queue)
        s -= 1

    return queue

N, M, P = map(int, input().split())
S = list(map(int, input().split()))
board = [list(input()) for _ in range(N)]
player = defaultdict(list)
castle = defaultdict(int)
dirs = [(0, 1), (1, 0), (-1, 0), (0, -1)]
total = N*M

for i in range(N):
    for j in range(M):
        if board[i][j].isdigit():
            player[board[i][j]].append((i, j))
            castle[board[i][j]] += 1
        if board[i][j] == '#':
            total -= 1

while is_finish():
    for i in range(1, P+1):
        p = str(i)
        if not player[p]:
            continue
        player[p] = bfs(player[p], p, S[i-1])

for i in range(1, P+1):
    print(castle[str(i)], end=' ')
print()