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

[문제]

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

이전 벽 부수고 이동하기 시리즈와는 상관없는 문제입니다.

 

처음에는 1인 위치마다 BFS를 사용하여 부르트포스하게 풀었습니다.

 

그 결과 시간 초과가 발생했고 최적화를 고민해야했습니다.

 

부르트포스하게 접근하는 방법을 생각했을 때를 생각하면, 공통되는 빈 공간을 지속적으로 탐색하는 상황이 발생하게 됩니다.

 

빈 공간은 유동적으로 바뀌는 것이 아니므로, 한 번 계산하면 해당 빈 공간과 인접한 다른 곳에서 탐색할 때 재탐색할 필요 없이 결과를 합산하면 됩니다.

즉 위와 같이 첫 1에서 출발해 0인 빈 공간을 탐색한 뒤에는, 나머지 인접한 1에서 해당 빈 공간을 탐색할 필요가 없다는 것입니다.

 

어디서 출발하는 탐색할 빈 공간의 크기는 3이 자명하기 때문입니다.

---

[초기화]

    def __init__(self):
        self.n, self.m = map(int, input().split())
        self.grid = [list(map(int, input())) for _ in range(self.n)]
        self.area = [[0] * self.m for _ in range(self.n)]

self.area는 분할된 공간을 표시하기 위한 2차원 리스트입니다.

---

[풀이]

    def check_range(self, y, x):
        return 0 <= y < self.n and 0 <= x < self.m and (y, x)

탐색 범위가 유효한지 확인합니다.

 

코드의 길이가 길어져서 따로 분리하였습니다.

    def search_area(self):
        dq = deque([])
        info = {}
        num = 1

        for y in range(self.n):
            for x in range(self.m):
                if self.grid[y][x] == 0 and self.area[y][x] == 0:  # 텅 빈 영역 탐색
                    dq.append((y, x))
                    self.area[y][x] = num
                    cnt = 1

                    while dq:
                        current_y, current_x = dq.popleft()
                        for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                            my, mx = current_y + dy, current_x + dx
                            if self.check_range(my, mx) and self.area[my][mx] == 0 and self.grid[my][mx] == 0:
                                dq.append((my, mx))
                                self.area[my][mx] = num
                                cnt += 1  # 영역의 수 갱신

                    info[num] = cnt  # 해당 영역 마킹
                    num += 1

        return info

1. 모든 공간을 순회하면서 빈 공간이자 아직 구분되지 않은 곳을 기점으로 탐색을 시작합니다.
2. BFS를 통해 공간 구분을 시작합니다.
3. 탐색이 끝나면 구분된 공간의 크기를 저장합니다.
4. 다음 공간과 구분하기 위해 공간의 번호를 갱신합니다.

    def get_result(self, info):
        for y in range(self.n):
            for x in range(self.m):
                if self.grid[y][x] == 1:
                    check_used = set()
                    for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                        my, mx = y + dy, x + dx
                        if self.check_range(my, mx):
                            num = self.area[my][mx]  # 해당 영역이 어디에 해당하는지
                            if num and num not in check_used:  # 텅 빈 영역이 아니고 아직 합산하지 않았다면
                                self.grid[y][x] += info[num]
                                check_used.add(num)
                    self.grid[y][x] %= 10

1. 벽을 기점으로 탐색을 시작합니다.
2. 벽과 인접한 공간의 번호를 찾아옵니다.
3. 해당 공간이 구분이 되어있고 아직 합산하지 않았다면 합산 처리합니다. 이후 사용 기록을 남깁니다.
   • 사용 기록을 남기는 이유는, 특정 벽이 동일한 공간과 2칸 이상 겹치는 경우가 있기 때문입니다.(테스트케이스 2)
   • 이런 경우 어디서 출발하든 한 번만 출발하면 되기 때문에, 처리가 되었다면 다음 탐색에서 제외하기 위함입니다.
4. 합산이 끝났다면 문제에서 제시된 대로 10으로 값을 나눕니다.

---

[전체 코드]

from collections import deque


class Main:
    def __init__(self):
        self.n, self.m = map(int, input().split())
        self.grid = [list(map(int, input())) for _ in range(self.n)]
        self.area = [[0] * self.m for _ in range(self.n)]

    def check_range(self, y, x):
        return 0 <= y < self.n and 0 <= x < self.m and (y, x)

    def search_area(self):
        dq = deque([])
        info = {}
        num = 1

        for y in range(self.n):
            for x in range(self.m):
                if self.grid[y][x] == 0 and self.area[y][x] == 0:  # 텅 빈 영역 탐색
                    dq.append((y, x))
                    self.area[y][x] = num
                    cnt = 1

                    while dq:
                        current_y, current_x = dq.popleft()
                        for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                            my, mx = current_y + dy, current_x + dx
                            if self.check_range(my, mx) and self.area[my][mx] == 0 and self.grid[my][mx] == 0:
                                dq.append((my, mx))
                                self.area[my][mx] = num
                                cnt += 1  # 영역의 수 갱신

                    info[num] = cnt  # 해당 영역 마킹
                    num += 1

        return info

    def get_result(self, info):
        for y in range(self.n):
            for x in range(self.m):
                if self.grid[y][x] == 1:
                    check_used = set()
                    for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                        my, mx = y + dy, x + dx
                        if self.check_range(my, mx):
                            num = self.area[my][mx]  # 해당 영역이 어디에 해당하는지
                            if num and num not in check_used:  # 텅 빈 영역이 아니고 아직 합산하지 않았다면
                                self.grid[y][x] += info[num]
                                check_used.add(num)
                    self.grid[y][x] %= 10

    def solve(self):
        info = self.search_area()
        self.get_result(info)

        print("\n".join("".join(map(str, i)) for i in self.grid))


problem = Main()
problem.solve()

---