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

문제 링크
https://www.acmicpc.net/problem/16946

문제 이해

이 문제는 이것만 알면 쉽게 풀 수 있다.

0. 인접한 빈 공간들을 하나의 집합으로 본다. (이하 빈 공간 집합)
1. 빈 공간 집합마다 고유 번호를 매긴다.
2. 각 빈 공간 집합마다 넓이를 구한다.
3. 모든 벽에 대하여
   3-1. 벽을 부쉈을 때 그 자리에 공간 하나 생기므로 +1
   3-2. 부순 벽 상하좌우에 있는 서로 다른 빈 공간 집합들의 넓이를 더함

예제 2의 빈 공간 집합은 다음과 같다.

풀이

1. 각 빈 공간 집합마다 고유 번호 매기기
   +
2. 각 빈 공간 집합마다 넓이를 구한다.

for i in range(n):
    for j in range(m):
        if not visit[i][j] and board[i][j] == 0:
            area += 1
            size_of_area[area] = bfs(i, j)

bfs 함수가 빈 공간 집합을 탐색하고 넓이를 반환한다.

3. 모든 벽에 대하여~

for i in range(n):
    for j in range(m):
        if board[i][j]:
            ans = 1 # 벽 부순 자리에 공간
            near = set() # '서로다른' 빈 공간 집합을 위해 set 사용
            for k in range(4):
                ny, nx = i + dy[k], j + dx[k]
                if in_range(ny, nx) and id_board[ny][nx]:
                    near.add(id_board[ny][nx]) # 빈 공간 집합의 고유 번호 넣어주기
            for id in near:
                ans += size_of_area[id] # 해당 빈 공간 집합의 넓이 더해주기
            ans_board[i][j] = ans % 10

정답 코드

import sys
from collections import deque

sys.setrecursionlimit(10 ** 8)
input = lambda: sys.stdin.readline().rstrip()

dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]


def in_range(y, x):
    return 0 <= y < n and 0 <= x < m


def bfs(y, x):
    cnt = 0
    q = deque([(y, x)])
    visit[y][x] = 1
    while q:
        cy, cx = q.popleft()
        id_board[cy][cx] = area
        cnt += 1
        for i in range(4):
            ny, nx = cy + dy[i], cx + dx[i]
            if in_range(ny, nx) and not visit[ny][nx] and board[ny][nx] == 0:
                visit[ny][nx] = 1
                q.append((ny, nx))

    return cnt


n, m = map(int, input().split())
board = [[] for _ in range(n)]
id_board = [[0 for _ in range(m)] for _ in range(n)]
ans_board = [[0 for _ in range(m)] for _ in range(n)]
visit = [[0 for _ in range(m)] for _ in range(n)]

area = 0
size_of_area = {}
for i in range(n):
    board[i] = list(map(int, input()))

for i in range(n):
    for j in range(m):
        if not visit[i][j] and board[i][j] == 0:
            area += 1
            size_of_area[area] = bfs(i, j)

for i in range(n):
    for j in range(m):
        if board[i][j]:
            ans = 1  # 벽 부순 자리에 공간
            near = set()  # '서로다른' 빈 공간 집합을 위해 set 사용
            for k in range(4):
                ny, nx = i + dy[k], j + dx[k]
                if in_range(ny, nx) and id_board[ny][nx]:
                    near.add(id_board[ny][nx])  #  빈 공간 집합의 고유 번호 넣어주기
            for id in near:
                ans += size_of_area[id]  # 해당 빈 공간 집합의 넓이 더해주기
            ans_board[i][j] = ans % 10

for i in range(n):
    for j in range(m):
        print(ans_board[i][j], end="")
    print()