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

https://www.acmicpc.net/problem/16946

문제

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

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

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

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

입력

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

출력

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

---

풀이

오랜만에 풀어보는 BFS 문제이다. 예전에 벽 부수고 이동하기 시리즈 풀면서 애를 좀 먹었었는데, 이번 벽부이 문제는 살짝 유형이 달랐다.

 

처음에는 다음과 같이 모든 칸에 대해서 BFS를 이용해서 갈 수 있는 칸의 개수를 그때그때 구하는 코드를 작성했었다.(단순 구현)

from collections import deque
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
graph = []
for i in range(N):
    graph.append(list(map(int, list(input().strip()))))
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
for i in range(N):
    for j in range(M):
        if graph[i][j] != 0:
            visited = [[0]*M for _ in range(N)]
            Q = deque()
            Q.append((i, j))
            visited[i][j] = 1
            while Q:
                x, y = Q.popleft()
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
                        if graph[nx][ny] == 0:
                            Q.append((nx, ny))
                            visited[nx][ny] = 1
            tmp = 0
            for k in visited:
                tmp += sum(k)
            print(tmp%10, end='')
        else:
            print(0, end='')
    print()

시간초과가 떴다.(당연히도)

골드2인데 이렇게 쉬울리가.

내가 생각하지 못한 다른 방법을 써야한다.

 

아이디어는 다음과 같다.

현재 칸이 1(벽)일때, 그 칸을 기준으로 상하좌우 칸들을 검사해서, 갈 수 있는 칸의 개수를 바로바로 구할 수 있도록 한다.

미리 BFS 작업을 다 해두고 나중에 필요할 때 쓴다는 것이다.

 

0(갈 수 있는 곳)으로 뭉쳐진 블럭(뭉탱이)를 만들고 각각의 뭉탱이에 고유 코드를 부여한다. 그리고 딕셔너리를 이용해서 그 뭉탱이가 몇 개의 0(갈 수 있는 곳)으로 이루어져있는지 저장하고 나중에 불러온다.

 

말로하면 이해가 안되는데

직접 보여주면 무슨 말인지 알기가 쉽다

 

예제 입력 2에 대한 것이다.

지금 이제 visited를 보여준 것인데 1이상의 자연수가 적혀있는 곳은 현재 벽이 없는 곳이다. 인접한 곳끼리는 같은 코드를 가지고 있는 것을 알 수 있다.

이 걸 이용하면 나중에 쉽게 벽이 있는 곳에 한해서 주변에 갈 수 있는 칸이 몇 개인지 빠르게 구할 수 있다.

 

최종 코드

 

from collections import deque
import sys

input = sys.stdin.readline
N, M = map(int, input().split())
graph = []
for i in range(N):
    graph.append(list(map(int, list(input().strip()))))
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

visited = [[0]*M for _ in range(N)]
groupnum = 1
dic = dict()
for i in range(N):
    for j in range(M):
        if graph[i][j] == 0 and not visited[i][j]:
            tmpcnt = 1
            Q = deque()
            Q.append((i, j))
            visited[i][j] = groupnum
            while Q:
                x, y = Q.popleft()
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
                        if graph[nx][ny] == 0:
                            Q.append((nx, ny))
                            visited[nx][ny] = groupnum
                            tmpcnt += 1
            dic[groupnum] = tmpcnt
            groupnum += 1



for i in range(N):
    for j in range(M):
        if graph[i][j] == 0:
            print(0, end='')
        else:
            ans = 0
            s = set()
            for k in range(4):
                nx = i + dx[k]
                ny = j + dy[k]
                if 0 <= nx < N and 0 <= ny < M:
                    if visited[nx][ny] != 0:
                        s.add(visited[nx][ny])
            s = list(s)
            for k in s:
                ans += dic[k]
            print((ans+1)%10, end='')
    print()

3트