백준 16946 파이썬 - 벽 부수고 이동하기 4

https://www.acmicpc.net/problem/16946

16946번: 벽 부수고 이동하기 4

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.

각각의 벽에 대해서 다음을 구해보려고 한다.

• 벽을 부수고 이동할 수 있는 곳으로 변경한다.
• 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

코드

from collections import deque
import sys
n, m = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(n)]
visited = [[False] * m for _ in range(n)]
zeros = [[0] * m for _ in range(n)]
group = 1
info = {}
info[0] = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(start):
    q = deque()
    q.append(start)
    cnt = 1
    while q:
        i, j = q.popleft()
        zeros[i][j] = group
        for idx in range(4):
            ni, nj = i + dy[idx], j + dx[idx]
            if ni < 0 or ni >= n or nj < 0 or nj >= m or visited[ni][nj] or board[ni][nj] == 1:
                continue
            visited[ni][nj] = True
            q.append((ni, nj))
            cnt += 1
    return cnt
for i in range(n):
    for j in range(m):
        if board[i][j] == 0 and not visited[i][j]:
            visited[i][j] = True
            w = bfs((i, j))
            info[group] = w
            group += 1
for i in range(n):
    for j in range(m):
        addList = set()
        if board[i][j]:
            for idx in range(4):
                ni, nj = i + dy[idx], j + dx[idx]
                if ni < 0 or ni >= n or nj < 0 or nj >= m:
                    continue
                addList.add(zeros[ni][nj])
            for add in addList:
                board[i][j] += info[add]
                board[i][j] %= 10
for i in board:
    sys.stdout.write("".join(map(str, i)))
    sys.stdout.write('\n')

풀이

그냥 bfs를 돌려 다 탐색하면 시간초과가 된다(아래 코드 참고). 따라서 0으로 이어져 있는 그룹을 찾아내 저장해야한다. 이렇게 하면 메모리 초과도 안뜨고 시간 초과도 안뜬다.

실패한 코드

import sys
from collections import deque
n, m = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(n)]
ones = [(i, j) for i in range(n) for j in range(m) if board[i][j] == 1]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(sx, sy):
    q = deque()
    q.append((sx, sy))
    visited = [[False for _ in range(m)] for _ in range(n)]
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if not board[nx][ny] and not visited[nx][ny]:
                    visited[nx][ny] = True
                    board[sx][sy] += 1
                    q.append((nx, ny))
for (i, j) in ones:
    bfs(i, j)
for i in board:
    sys.stdout.write(''.join(str(j % 10) for j in i))
    sys.stdout.write('\n')

더 간단해 보이는 코드고 출력 결과도 잘 나오지만 메모리초과나 시간 초과가 계속 떴다.