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

 

 

문제

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

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

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

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

 

 

 

 

난이도

골드 2

 

 

 

 

코드

import sys
from collections import deque

n, m = map(int,sys.stdin.readline().split())
graph = []
group_width = [0,0] # 그룹번호의 너비를 담는 리스트
group_num = 2
move = [(-1,0),(1,0),(0,1),(0,-1)]
for _ in range(n) :
    x = list(map(int,sys.stdin.readline().rstrip()))
    graph.append(x)

for i in range(n) :
    for j in range(m) :
        if graph[i][j] == 0 :
            # BFS해서 그룹번호 저장
            cnt = 1
            graph[i][j] = group_num
            queue = deque()
            queue.append((i,j))

            while queue :
                x, y = queue.popleft()
                for xx, yy in move :
                    X = x + xx
                    Y = y + yy
                    if 0 <= X < n and 0 <= Y < m :
                        if graph[X][Y] == 0 :
                            queue.append((X,Y))
                            graph[X][Y] = group_num
                            cnt += 1

            group_width.append(cnt)
            group_num += 1

new_graph = [[0 for _ in range(m)] for _ in range(n)]

for i in range(n) :
    for j in range(m) :
        if graph[i][j] == 1 :
            add_list = set()
            for a, b in move :
                I = i + a
                J = j + b
                if 0 <= I < n and 0 <= J < m :
                    add_list.add(graph[I][J])
            for al in add_list :
                new_graph[i][j] += group_width[al]
            new_graph[i][j] += 1
            new_graph[i][j] %= 10

for x in new_graph :
    print("".join(map(str,x)))

 

 

 

 

풀이과정

1. 그래프를 순환하며 0이 모여있는 곳의 너비를 BFS를 통해 구한다.

2. 그래프에는 0이 있던 곳에 해당 그룹 번호를 저장해두고, 그룹 번호에 해당하는 너비를 리스트에 따로 저장해둔다.

3. 그래프를 순환하며 상하좌우 인접한 그룹번호들을 찾아내어 그룹번호에 해당하는 너비들을 더한다.

 

그룹 번호를 저장하고, 그룹 번호에 대한 너비를 따로 저장해두었으며 중복 계산을 막기위해 set()을 사용했다는 점을 기억해두면 좋을 것 같다.