16946. 벽 부수고 이동하기 4

업데이트 시간 : 2023-03-23 08:21:57 +0000

[Gold II] 벽 부수고 이동하기 4 - 16946

성능 요약

메모리: 224392 KB, 시간: 664 ms

분류

그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

문제 설명

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

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

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

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

입력

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

출력

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

💡 Solutions

📄 벽 부수고 이동하기 4.py

from collections import deque

N,M = map(int,input().split())
ans = list()
matrix = list()
is_travel = list()
blocks = list()
for i in range(N):
    row = list(map(int,input()))
    row_ = []
    _row = []
    matrix.append(row)
    for j in range(M):
        if row[j]:
            blocks.append((i,j))
        row_.append(0)
        _row.append(False)
    ans.append(row_)
    is_travel.append(_row)


groups = dict()
group = 10
def bfs(start):
    global group
    cnt = 1
    que = deque()
    que.append(start)
    is_travel[start[0]][start[1]] = True

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

        for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
            nx = x + dx
            ny = y + dy

            if nx < 0 or ny < 0 or nx>=N or ny>= M:continue
            if matrix[nx][ny] == 1: continue
            if is_travel[nx][ny] :continue
            is_travel[nx][ny] = True
            matrix[nx][ny] = group
            que.append((nx,ny))
            cnt += 1
        
    groups[group] = cnt
    group += 1

    return cnt

for a in range(N):
    for b in range(M):
        if matrix[a][b] == 0:
            matrix[a][b] = group
            bfs((a,b))

# print(groups)
for block in blocks:
    group_visited = set()
    link = 1
    for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
        nx = block[0] + dx
        ny = block[1] + dy

        if nx < 0 or ny < 0 or nx>=N or ny>= M:continue
        if matrix[nx][ny] == 1 : continue
        group_visited.add(matrix[nx][ny])

    for k in group_visited:
        link += groups[k]
    # matrix[block[0]][block[1]] = 0
    ans[block[0]][block[1]] = link%10
    # matrix[block[0]][block[1]] = 1

# for row in matrix:
#     print(*row)
# print()
for row in ans:
    print(*row,sep='')