백준 16920 확장 게임

from collections import deque
import sys

input = sys.stdin.readline

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

n, m, p = map(int, input().split())
s = [0] + list(map(int, input().split()))
for i in range(len(s)):
    if s[i] > n * m:
        s[i] = n * m
g = [list(input()) for _ in range(n)]

castle = [[] for _ in range(p+1)]

cnt = 0

for i in range(n):
    for j in range(m):
        if g[i][j] == '.':
            cnt += 1
            continue
        elif g[i][j] == '#':
            continue
        else:
            castle[int(g[i][j])].append((i, j))
            cnt += 1

def fin():
    scastle = 0
    for i in range(1, p+1):
        scastle += len(castle[i])
    if scastle == cnt:
        return True
    return False

def expand(turn):
    check = [[-1] * m for _ in range(n)]
    q = deque()
    for a, b in castle[turn]:
        q.append((a, b))
        check[a][b] = 0
    while q:
        x, y = q.popleft() 
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
            if check[nx][ny] != -1 or g[nx][ny] != '.':
                continue
            check[nx][ny] = check[x][y] + 1
            if check[nx][ny] < s[turn]:
                q.append((nx, ny))
            castle[turn].append((nx, ny))
            g[nx][ny] = str(turn)

turn = 1

while fin() == False:
    if turn == p + 1:
        turn = 0
    expand(turn)
    turn += 1

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

그냥 성의 좌표를 리스트에 넣어서 그 리스트에 있는 성들을 시작점으로해서 bfs 돌리는 간단한 생각으로 풀었는데 시간초과 -> 성들이 최대 1000의 제곱개 있는데 거기서 다시 일일이 bfs-> 시간초과

from collections import deque
import sys

input = sys.stdin.readline

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

n, m, p = map(int, input().split())

s = [0] + list(map(int, input().split()))

g = [list(input()) for _ in range(n)]

castle = [[] for _ in range(p+1)]
tmp_castle = [[] for _ in range(p+1)]
cnt = 0

for i in range(n):
    for j in range(m):
        if g[i][j] == '.':
            cnt += 1
            continue
        elif g[i][j] == '#':
            continue
        else:
            castle[int(g[i][j])].append((i, j))
            tmp_castle[int(g[i][j])].append((i, j))
            cnt += 1
def fin():
    rans = 0
    for i in range(1, p+1):
        rans += len(tmp_castle[i])
    if rans == 0:
        return True
    return False

def expand(turn):
    check = [[-1] * m for _ in range(n)]
    q = deque()
    for a, b in tmp_castle[turn]:
        q.append((a, b))
        check[a][b] = 0
    tmp_castle[turn].clear()
    while q:
        x, y = q.popleft() 
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
            if check[nx][ny] != -1 or g[nx][ny] != '.':
                continue
            check[nx][ny] = check[x][y] + 1
            if check[nx][ny] < s[turn]:
                q.append((nx, ny))
            tmp_castle[turn].append((nx, ny))
            g[nx][ny] = str(turn)

turn = 1
while fin() == False:
    if turn == p + 1:
        turn = 0
    expand(turn)
    for i in range(len(tmp_castle[turn])):
        castle[turn].append(tmp_castle[turn][i])
    turn += 1
for i in range(1, p+1):
    print(len(castle[i]), end=' ')

tmp_castle 이라는 새로 추가된 성의 리스트 를 만들어서 그 곳에서만 bfs를 시작하도록 하였다. 시간 초과 해결