[백준/python] 2234 성곽

import sys
input = sys.stdin.readline 


def dfs():
    tmp = 0 
    stack = [(i,j)]
    while stack:
        x,y = stack.pop()
        if visit[x][y]: continue
        visit[x][y] = cnt
        tmp += 1
        for b in range(4):
            if not arr[x][y]&1<<b:
                dx,dy = dr[b]
                di,dj = x+dx,y+dy
                if not visit[di][dj]:
                    stack.append((di,dj))
    data[cnt]=tmp
    return tmp

dr = (0,-1),(-1,0),(0,1),(1,0)

M,N = map(int,input().split())
arr = [[*map(int,input().split())] for _ in range(N)]

visit =  [[0]*M for _ in range(N)]
data = dict()
cnt = 0
max_v = 0
for i in range(N):
    for j in range(M):
        if not visit[i][j]:
            cnt += 1
            max_v = max(max_v, dfs())

max_sum = 0
for i in range(N):
    for j in range(M):
        for dx,dy in dr:
            di,dj = i+dx,j+dy
            if 0<=di<N and 0<=dj<M:
                if visit[i][j] == visit[di][dj]: continue
                max_sum=max(max_sum, data[visit[i][j]]+data[visit[di][dj]])

print(cnt)
print(max_v)
print(max_sum)

전체를 순회하는 탐색 문제에서, 비트마스킹을 더한 문제입니다.

크게 사용된 알고리즘은 3가지 입니다.

1. DFS

일반적으로 배열을 탐색하는 경우 BFS를 사용하는 것이 일반적입니다.
하지만 문제에서 주어지는 배열의 크기가 1 <= M,N <= 50 으로 매우 작기 때문에 deque를 불러오는 것이 더 걸릴 것이라 판단하여 리스트를 활용한 DFS로 탐색을 진행했습니다.

2. 비트마스킹

입력으로 주어지는 리스트는 각 방향을 1,2,4,8 로 두고 벽이 있는 방향의 총 합을 나타냅니다. 따라서 델타 탐색을 할 때, 벽이 있는지 여부를 비트 연산으로 확인하여 탐색을 진행하게 됩니다.

3. 플러드 필

문제에서 요구하는 방의 개수를 계산하기 위해 cnt 변수를 1씩 올려가며 탐색함과 동시에 visit배열에cnt로 방문 표시를 함으로써 각 칸에 cnt로 주소를 부여했습니다.

또한, 문제에서 요구하는 가장 큰 방의 크기 max_v를 계산하기 위해 방의 크기를 tmp 변수에 넣어 비교하는 동시에, 각 칸의 크기를 data 딕셔너리에 넣어 계산된 tmp 값을 저장해둡니다.

이를 통해 마지막으로 한 번 더 순회하면서 인접한 칸의 visit에 저장된 값이 다른 경우, 둘을 합치고 max_sum 에서 최대값을 비교함으로써 원하는 세 가지의 값을 모두 찾을 수 있습니다.