[백준: Python] 2234 - 성곽

[문제]

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

그래프 탐색에 비트마스킹이 합쳐진 독특한 문제였습니다.

 

문제에서 비트에 대한 언급이 있어서 쉽게 풀 수 있었지, 없었다면 쉽게 감을 잡지 못했을 것입니다.

 

오랜만에 시간을 재고 풀어본 문제로, 구조화 30분, 풀이 및 디버깅 1시간 소요했습니다.

---

[초기화]

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

grid는 디버깅을 위한 자료구조로, 실제 탐색이 제대로 이루어졌는지 확인하기 위해 선언하였습니다.

추후 해당 자료구조는 벽을 제거했을 때 가장 넓은 방의 크기를 구할 때 사용됩니다.

 

area는 각 방의 크기를 저장하는 리스트로, 방을 1번부터 표현하기 위해 더미값을 추가했습니다.

 

answer는 순서대로 문제에서 요구하는 답을 저장하게 됩니다.

---

[풀이]

    def search(self, y, x, num):
        directions = [(0, -1), (-1, 0), (0, 1), (1, 0)]  # 서북동남
        dq = deque([(y, x)])
        self.visited[y][x] = True
        self.grid[y][x] = num
        size = 1  # 방의 넓이

        while dq:
            current_y, current_x = dq.popleft()
            current_info = self.origin[current_y][current_x]  # 벽 정보
            for i in range(4):
                if current_info & (1 << i) == 0:
                    dy, dx = directions[i]
                    my, mx = current_y + dy, current_x + dx
                    if 0 <= my < self.m and 0 <= mx < self.n and not self.visited[my][mx]:
                        self.visited[my][mx] = True
                        self.grid[my][mx] = num
                        size += 1
                        dq.append((my, mx))

        self.area.append(size)  # 각 영역의 넓이
        self.answer[1] = max(self.answer[1], size)

주어진 위치에서 탐색을 시작합니다.

1. 탐색하는 위치의 값을 비트를 체크합니다.
   • 비트를 순차적으로 시프트하여 현재 위치값과 비교합니다. 이때 and 연산 시 값이 0이면 벽에 막힌 부분이 없다는 것을 의미합니다.
     
     예를 들어, 현재 위치값이 11이라면 비트 표현시 1011입니다. 이때 2^2(1 << 2)에 해당하는 부분이 0이므로 동쪽이 뚫려있다는 것을 알 수 있습니다.
     
     그렇다면 각 방향에 대해 and 연산을 이용해 순차적으로 확인했을 때 다음과 같은 결과를 확인할 수 있습니다.
     1011 & 0001 = 0000 = 1
     1011 & 0010 = 0010 = 2
     1011 & 0100 = 0000 = 0
     1011 & 1000 = 1000 = 8
2. 위에 방식을 통해 이동할 수 있는 곳을 찾아 BFS를 수햅합니다.
   • BFS 과정에서 방을 구분하기 위해 주어진 숫자(num)를 표시하며 이동한 방들의 수를 합산합니다.
3. 탐색이 종료되면 구한 방의 넓이를 저장합니다.
4. 지금까지 확인된 방의 최대 넓이와 현재 넓이와 비교하여 큰 값으로 갱신합니다.

    def find_max_area(self):
        for y in range(self.m):
            for x in range(self.n):
                for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    my, mx = y + dy, x + dx
                    if 0 <= my < self.m and 0 <= mx < self.n:
                        idx1, idx2 = self.grid[y][x], self.grid[my][mx]
                        if idx1 != idx2:  # 마주한 영역의 값이 다르면
                            self.answer[2] = max(self.answer[2], self.area[idx1] + self.area[idx2])  # 두 영역의 합

방들의 영역이 탐색을 통해 구분되었다면 벽을 허물었을 때 최대 방의 크기를 계산합니다.

 

모든 영역은 벽이거나 벽이 아니기 때문에 인접한 영역과 비교했을 때 값이 다르다면, 벽이 있는 것으로 간주합니다.

 

이를 이용해 현재 방의 크기와 인접한 방의 크기를 합산하여 최대 크기를 찾아냅니다.

---

[전체 코드]

from collections import deque


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

    def search(self, y, x, num):
        directions = [(0, -1), (-1, 0), (0, 1), (1, 0)]  # 서북동남
        dq = deque([(y, x)])
        self.visited[y][x] = True
        self.grid[y][x] = num
        size = 1  # 방의 넓이

        while dq:
            current_y, current_x = dq.popleft()
            current_info = self.origin[current_y][current_x]  # 벽 정보
            for i in range(4):
                if current_info & (1 << i) == 0:
                    dy, dx = directions[i]
                    my, mx = current_y + dy, current_x + dx
                    if 0 <= my < self.m and 0 <= mx < self.n and not self.visited[my][mx]:
                        self.visited[my][mx] = True
                        self.grid[my][mx] = num
                        size += 1
                        dq.append((my, mx))

        self.area.append(size)  # 각 영역의 넓이
        self.answer[1] = max(self.answer[1], size)

    def find_max_area(self):
        for y in range(self.m):
            for x in range(self.n):
                for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    my, mx = y + dy, x + dx
                    if 0 <= my < self.m and 0 <= mx < self.n:
                        idx1, idx2 = self.grid[y][x], self.grid[my][mx]
                        if idx1 != idx2:  # 마주한 영역의 값이 다르면
                            self.answer[2] = max(self.answer[2], self.area[idx1] + self.area[idx2])  # 두 영역의 합

    def solve(self):
        num = 0
        for y in range(self.m):
            for x in range(self.n):
                if not self.visited[y][x]:
                    num += 1
                    self.answer[0] += 1
                    self.search(y, x, num)

        self.find_max_area()
        print(self.answer[0])
        print(self.answer[1])
        print(self.answer[2])


problem = Main()
problem.solve()

처음에는 코드를 부르트포스하게 작성했습니다.

 

벽이 있는지 검사하는 과정도 반복문이 아니라 동일한 포맷의 코드를 4번이나 작성했습니다.

 

또한 벽을 뚫는 과정도 합산 형식이 아니라, 모든 좌표를 순회하며 벽을 뚫었을 때 가장 큰 넓이를 찾는 방식을 택했습니다.

 

N과 M의 크기가 작아서 해당 방식으로 통과가 됐지만 약 14배의 시간차이가 났습니다.

---