[BOJ] 백준 2234번 문제 풀이 (Python)

1. 문제 풀이

DFS∙BFS에 비트마스킹을 활용하는 문제였다. 3가지 정답을 구해야했다.

1. 이 성에 있는 방의 갯수
   • 성을 (0,0) → (m-1,n-1)를 이중 for 반복문을 이용해 탐색하면서 방문하지 않은 곳이 있다면 처음 만나는 방이므로 bfs를 이용해 방의 넓이를 구하였다.
   • bfs를 사용한 횟수가 방의 갯수를 의미한다.
   • 비트마스킹을 사용해 갈 수 없는 방향을 쉽게 구할 수 있었다.
     • 예를 들어 현재 칸의 숫자가 11이라고 한다면 11 & (1 « 0) , 11 & (1 « 1), 11 & (1 « 3)에서 True가 나올 것이다.
2. 가장 넓은 방의 넓이
   • bfs를 이용해 구한 방의 넓이를 하나의 배열에 모두 담고 배열의 최댓값을 구하였다.
3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기
   • bfs를 이용해 인접한 방의 넓이를 구하였다. (bfs를 이용하지 않아도 구할 수 있을 것 같다.)

2. 코드

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def bfs(i, j, number):
    q = deque([(i,j,1)])
    splitted[i][j] = number
    result = [(i, j)]
    while q:
        y, x, area = q.popleft()
        for idx in range(4):
            if matrix[y][x] & (1 << idx): continue
            dy, dx = y + my[idx], x + mx[idx]
            if 0 <= dy < m and 0 <= dx < n and not splitted[dy][dx]:
                splitted[dy][dx] = number
                result.append((dy, dx))
                q.append((dy,dx,area+1))
    return len(result)

def find_connected_area():
    visited = [[0] * n for _ in range(m)]
    q = deque([(0,0, splitted[0][0])])
    max_area = 0
    while q:
        y, x, number1 = q.popleft()
        for idx in range(4):
            dy, dx = y + my[idx], x + mx[idx]
            if 0 <= dy < m and 0 <= dx < n and not visited[dy][dx]:
                number2 = splitted[dy][dx]
                visited[dy][dx] = 1
                q.append((dy,dx,number2))
                if number1 != number2 and max_area < (areas[number1] + areas[number2]):
                    max_area = areas[number1] + areas[number2]
    return max_area

n, m = map(int,input().split()) # 너비, 높이
matrix = [ list(map(int,input().split())) for _ in range(m)]
my = [0,-1,0,1]
mx = [-1,0,1,0]

splitted = [[0] * n for _ in range(m)]
cnt = 0
areas = [0]
for i in range(m):
    for j in range(n):
        if not splitted[i][j]:
            cnt += 1
            areas.append(bfs(i,j,cnt))

print(cnt)
print(max(areas))
print(find_connected_area())