[백준/BOJ] gold2 - 16946번 벽 부수고 이동하기 4 (Python)

▶16946 - 벽 부수고 이동하기 4

▶문제

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

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

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

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

 

▶입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.

 

▶출력

맵의 형태로 정답을 출력한다. 원래 빈칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.

 

▶예제

 

▶풀이

0의 모음들을 먼저 찾았다.

그다음에 1 위아래 양옆 이렇게 4개 방향으로 0의 group을 파악한 후에 수를 더해줬다.

이때 같은 그룹의 0이 동시에 접할 수도 있기 때문에 그 부분을 빼주기 위해서 set을 사용했다.

from collections import deque
direct = [(-1, 0), (1, 0), (0, -1), (0, 1)]


def bfs(x, y):
    queue = deque()
    queue.append([x, y])
    visit[x][y] = 1
    count = 1
    while queue:
        cur_x, cur_y = queue.pop()
        zero[cur_x][cur_y] = group
        for dx, dy in direct:
            nx, ny = cur_x + dx, cur_y + dy
            if 0 <= nx < n and 0 <= ny < m and \
                    visit[nx][ny] == 0 and maps[nx][ny] == 0:
                queue.append([nx, ny])
                visit[nx][ny] = 1
                count += 1
    return count


n, m = map(int, input().split())
maps = []
visit = [[0 for _ in range(m)] for _ in range(n)]
zero = [[0 for _ in range(m)] for _ in range(n)]
for i in range(n):
    maps.append(list(map(int, input().rstrip())))

group = 1
group_z = {}
for i in range(n):
    for j in range(m):
        if maps[i][j] == 0 and visit[i][j] == 0:
            group_z[group] = bfs(i, j)
            group += 1
result = [[0 for _ in range(m)] for _ in range(n)]
for i in range(n):
    for j in range(m):
        cnt = 1
        if maps[i][j] == 0:
            continue
        position_4 = set()
        for dx, dy in direct:
            nx, ny = i + dx, j + dy
            if 0 <= nx < n and 0 <= ny < m and \
                    maps[nx][ny] == 0:
                position_4.add(zero[nx][ny])
        for k in position_4:
            cnt += group_z[k]
            cnt %= 10
        result[i][j] = cnt
for re in result:
    for r in re:
        print(r, end='')
    print()