[백준] 16946 - 벽 부수고 이동하기 4 (G2)

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

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

이 문제는 그래프 탐색 문제를 조금 꼬아낸 문제이다.

제일 나이브한 풀이는 각 벽에 대해 BFS를 수행하는 것인데, 아무리 봐도 이건 시간 초과 풀이이다.

전체 영역이 최대 100만 칸짜리 2차원 배열인데, 이를 중복해서 순회하면 시간 초과가 안날 수 없다.

 

2차원배열을 한번만 순회하여, 그 결과를 이용해 답을 도출해야 한다.

그래서 나는 비어있는 영역에 대해 BFS를 수행하여 넓이를 미리 구해놓고,

벽에 대해 상하좌우를 확인하여 빈공간이 있을 경우, 해당 빈 공간이 속해있는 영역 사이즈를 더해주도록 했다.

 

이때 주의 할 점은

00

01

이렇게 그래프가 있다고 한다면, 벽의 왼쪽 빈공간과, 벽의 위쪽 빈공간이 같은 영역에 속해 있기 때문에

중복해서 세지 않도록 각 빈공간이 속한 '영역(그룹)'을 잘 구분해줘야 한다.

 

이걸 이제 어떻게 구현하느냐는 사람마다 다르겠지만, 나는 분리집합 아이디어를 살짝 차용했다.

(실제 분리집합을 구현하진 않았다.)

 

위 예시에서

00

01

분리집합의 대표 원소로 '빈공간의 좌표'를 설정했다.

그러면 초기 분리집합의 데이터는 아래와 같이 들어있었을 것이다.

(1, 1)은 빈공간이 아니니 사실상 무시된다.

(0, 0) (0, 1)

(1, 0) (1, 1)

 

그리고 (0, 0)에 대해 BFS를 수행하고, 이 과정에서 방문한 모든 정점의 부모를 (0, 0)으로 넣어준다.

(0, 0) (0, 0)

(0, 0) (1, 1)

 

그리고 BFS를 수행하면서 정점을 방문할 때마다 이 그룹의 영역 넓이를 1씩 증가시켜준다.

그럼 (0, 0) 이라는 그룹의 영역 넓이는 3이되고

(0, 1) (1, 0) 이 속한 영역의 넓이를 구하기 위해 (0, 0)의 영역의 넓이를 구하게끔 하면 된다.

 

이때 중복된 영역의 넓이를 더해주지 않도록 하기 위해 'Set' 자료구조를 활용하여

한번 방문한 영역 그룹은 중복하여 방문하지 않게 하면 답을 구할 수 있다.

 

import sys
from collections import deque
input = sys.stdin.readline
TEST_MODE = False
dx = di = [1, -1, 0, 0]
dy = dj = [0, 0, 1, -1]


def print_board(board, n, desc=""):
    if desc:
        print(desc)
    for i in range(n):
        print(*board[i])
    print()


def solve():
    # input
    n, m = map(int, input().split())
    board = [list(map(int, list(input().rstrip()))) for _ in range(n)]
    if TEST_MODE:
        print_board(board, n)

    # BFS Settings
    visit = [[False for _ in range(m)] for _ in range(n)]
    parent = [[(i, j) for j in range(m)] for i in range(n)]
    area_at = [[0 for _ in range(m)] for _ in range(n)]
    d = deque()

    # board 내 각각의 빈 공간에 대해서 BFS 수행하여 넓이 구하기
    for i in range(n):
        for j in range(m):
            if board[i][j] == 0 and not visit[i][j]:
                d.append((i, j))
                visit[i][j] = True
                area = 1
                while d:
                    now_i, now_j = d.popleft()
                    for k in range(4):
                        check_i, check_j = now_i + di[k], now_j + dj[k]
                        if 0 <= check_i < n and 0 <= check_j < m:
                            if not visit[check_i][check_j] and board[check_i][check_j] == 0:
                                parent[check_i][check_j] = (i, j)
                                visit[check_i][check_j] = True
                                d.append((check_i, check_j))
                                area += 1
                area_at[i][j] = area
    if TEST_MODE:
        print_board(parent, n, "parent")
        print_board(visit, n, "visit")
        print_board(area_at, n, "area_at")

    # answer count
    for i in range(n):
        for j in range(m):
            if board[i][j] == 1:
                s = set()
                for k in range(4):
                    check_i = i + di[k]
                    check_j = j + dj[k]
                    if 0 <= check_i < n and 0 <= check_j < m and board[check_i][check_j] == 0:
                        area_pos = parent[check_i][check_j]
                        if area_pos not in s:
                            s.add(area_pos)
                            board[i][j] += area_at[area_pos[0]][area_pos[1]]
                            board[i][j] %= 10

    # print answer
    for i in range(n):
        for j in range(m):
            print(board[i][j], end='')
        print()


if __name__ == '__main__':
    solve()