이번 문제는 BFS를 이용하여 해결하였다. 처음에는 1과 2를 4 방향으로 퍼트리며 임시 큐에 퍼진 위치를 저장하고, 그 위치를 초기의 1과 2의 위치를 저장한 큐에 다시 넣는 방식을 사용했다. 2를 퍼트릴 때 퍼트리려는 좌표가 1의 위치를 저장한 좌표에 존재할 경우 그 좌표를 3으로 변경하도록 하였다. 그러나 시간초과가 발생하였다.

그래서 새로생각한 방법은 set의 연산을 활용하는 것이었다. 4 방향으로 1과 2를 퍼트릴 때, 1과 2의 다음 위치에 대한 임시 set에 좌표를 저장하고, 3의 좌표를 1과 2의 set의 & 연산자 결과로 얻어내는 것이었다. 이 방식을 통해 중복된 좌표의 확인을 줄일 수 있었고 & 연산을 통해 쉽게 3의 좌표를 얻을 수 있었다.

Code

from collections import deque
n, m=map(int, input().split())
grid=[list(map(int, input().split())) for _ in range(n)]
one, two=deque(), deque()
for i in range(n):
    for j in range(m):
        if grid[i][j]==1:
            one.append((i, j))
        if grid[i][j]==2:
            two.append((i, j))
dy, dx=[0, 1, 0, -1], [1, 0, -1, 0]
cnt=[len(one), len(two), 0]
def bfs():
    set1, set2, set3=set(), set(), set()
    while one:
        y, x=one.popleft()
        for i in range(4):
            ny, nx=y+dy[i], x+dx[i]
            if 0<=ny<n and 0<=nx<m and grid[ny][nx]==0:
                set1.add((ny, nx))
    while two:
        y, x=two.popleft()
        for i in range(4):
            ny, nx=y+dy[i], x+dx[i]
            if 0<=ny<n and 0<=nx<m and grid[ny][nx]==0:
                set2.add((ny, nx))
    set3=set1&set2
    for y, x in set3:
        grid[y][x]=3
        cnt[2]+=1
    for y, x in set1-set3:
        grid[y][x]=1
        one.append((y, x))
        cnt[0]+=1
    for y, x in set2-set3:
        grid[y][x]=2
        two.append((y, x))
        cnt[1]+=1
while one or two:
    bfs()
print(*cnt)