[Python/파이썬] 백준 16946번: 벽 부수고 이동하기 4

문제

 

풀이

1. 0의 묶음을 그룹으로 표시해준다.

 

2. 각 그룹별로 0의 개수가 몇 개인지 dict를 통해 저장한다.

 

3. 벽(1)에서 상하좌우로 인접한 그룹을 구한 뒤, 그 그룹에 해당하는 0의 개수를 더해준다.

그룹이 중복되지 않게 set()을 사용한다.

코드

from collections import deque
input = __import__('sys').stdin.readline

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 graph[ni][nj] == 1:
                continue
            visited[ni][nj] = True
            q.append((ni, nj))
            cnt += 1
    return cnt

n, m = map(int, input().split())
graph = [list(map(int, input().strip())) 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 = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

for i in range(n):
    for j in range(m):
        if graph[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 graph[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:
                graph[i][j] += info[add]
                graph[i][j] %= 10

for g in graph:
    print("".join(map(str, g)))

 

마무리

너무 어려워서 벽 느꼈다...

혼자서는 도저히 못 풀었을 문제ㅠ