[백준 16946] 벽 부수고 이동하기 4(Python)

1. 요약

문제 참고(https://www.acmicpc.net/problem/16946)

2. 아이디어

NxM 정답 배열을 만들고 임의 좌표 y,x에 대해 정답배열[y][x]가 벽이면 값을 1로 바꾼다.
그리고 맵을 탐색하면서 0을 가리키는 위치를 찾고 그 위치가 처음 방문한 곳이면, bfs를 한다.

bfs에서 알아야 하는 것은 0의 개수와 0과 인접한 벽(들)의 좌표이다. bfs가 종료되면, 0의 개수를 인접한 벽들의 좌표를 의미하는 y,x에 대해, 정답배열[y][x] += 0의 개수를 한다. 만약 결과가 10이상이면, 10을 나눈 나머지를 저장한다.

3. 코드

import sys
from collections import deque

r, c = map(int, sys.stdin.readline().rsplit())
visited = [[False for _ in range(c)] for _ in range(r)]
arr = [list(map(int, list(sys.stdin.readline().rstrip()))) for _ in range(r)]
answer = [[0 for _ in range(c)] for _ in range(r)]
d = ((0,1), (0,-1), (1,0), (-1,0))

for i in range(r):
    for j in range(c):
        if arr[i][j] == 1: answer[i][j] = 1

def bfs(sy, sx):
    q = deque()
    q.append((sy, sx))
    cnt = 1
    ones = []

    while q:
        y, x = q.popleft()

        for i in range(4):
            ny = y + d[i][0]
            nx = x + d[i][1]

            if -1<ny<r and -1<nx<c:
                if visited[ny][nx]: continue
                visited[ny][nx] = True

                if arr[ny][nx] == 0:                  
                    visited[ny][nx] = True
                    q.append((ny,nx))
                    cnt += 1

                else: ones.append((ny, nx))
    
    for y, x in ones:
        visited[y][x] = False
        answer[y][x] += cnt
        if answer[y][x] >= 10: answer[y][x] %= 10

for i in range(r):
    for j in range(c):
        if arr[i][j] == 0:
            if not visited[i][j]:
                visited[i][j] = True
                bfs(i,j)

for i in range(r):
    print(''.join(map(str,answer[i])))