[골드 2] 16946번: 벽 부수고 이동하기 4

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

16946번: 벽 부수고 이동하기 4

---

문제

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

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

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

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

입력

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

출력

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

---

풀이

Naive하게 '모든 칸을 순회하면서 벽이 나오면 BFS를 돌리자' 라고 생각하면 시간 초과가 뜬다. 적어도 Python으로는 그렇다. 다른 방법으로 접근해야 한다.

우선 미로를 순회하면서 빈 칸을 먼저 찾는다. 빈 칸이 나오면 BFS를 돌려서 해당 칸이 속한 빈 영역을 찾아 표시한다. 정수형 사전 자료형을 사용해 영역을 {key : area} 형태로 저장하고, 표시할 때는 미로와 같은 크기의 2차원 List에 Key값을 표시하면 된다. 모든 칸을 순회했으면 이제 벽을 찾아서 해당 벽의 상하좌우에 있는 빈 영역의 넓이를 다 더해준다. 이때 같은 영역의 넓이를 중복해서 더하지 않도록 주의한다.

내가 작성한 소스코드

# Pypy3로 제출

import sys
from collections import deque
r = sys.stdin.readline


def bfs(board, target_board, num, start_pos, d, size):
    y = start_pos[0]; x = start_pos[1]
    n = size[0]; m = size[1]
    blanks_cnt = 0

    q = deque()
    q.append((y, x))
    target_board[y][x] = num
    blanks_cnt += 1
    
    while q:
        (y, x) = q.popleft()

        for (dy, dx) in d:
            ny = y + dy
            nx = x + dx

            if (ny < 0 or ny > n-1) or (nx < 0 or nx > m-1):
                continue

            if target_board[ny][nx] > 0 or board[ny][nx] == 1:
                continue

            q.append((ny, nx))
            target_board[ny][nx] = num
            blanks_cnt += 1
    
    return blanks_cnt

def get_blanks(board, blank_dict, pos, d, size):
    y = pos[0]; x = pos[1]
    n = size[0]; m = size[1]
    blanks_cnt = 1
    blanks_to_add = set()

    for (dy, dx) in d:
        ny = y + dy
        nx = x + dx

        if (ny < 0 or ny > n-1) or (nx < 0 or nx > m-1) or board[ny][nx] < 0:
            continue

        blanks_to_add.add(board[ny][nx])

    for v in blanks_to_add:
        blanks_cnt += blank_dict[v]

    return blanks_cnt % 10


n, m = map(int, r().split())
maze = []
for _ in range(n):
    maze.append(list(map(int, r().rstrip())))
blanks = dict(); blank_key = 0
maze_blanks = [[-1] * m for _ in range(n)]
d = ((-1, 0), (0, -1), (1, 0), (0, 1))

for i in range(n):
    for j in range(m):
        if maze[i][j] == 0 and maze_blanks[i][j] == -1:
            blank_key += 1
            blanks[blank_key] = bfs(maze, maze_blanks, blank_key, (i, j), d, (n, m))

for i in range(n):
    for j in range(m):
        if maze[i][j] == 1:
            maze[i][j] = get_blanks(maze_blanks, blanks, (i, j), d, (n, m))

for row in maze:
    print("".join(map(str, row)))

남이 작성한 소스코드

koosaga 님:
https://www.acmicpc.net/source/12130779

피드백

• C++을 배워서 Python으로 풀었을 때 시간 초과가 날 것 같은 문제들은 C++로 풀자. 분명 Logic은 맞는데 시간 초과 때문에 틀리면 억울하다.
• 긴 조건문을 반복해서 사용할 때는 조건문을 함수화해서 코드의 가독성을 높일 수 있다.