백준 2234 성곽

from collections import deque

n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(m)]
dy = [-1, 0, 1, 0]
dx = [0, -1, 0, 1]
group = 0
check = [[0] * n for _ in range(m)]

def bfs(i, j, group):
    q = deque()
    q.append((i, j))
    check[i][j] = group
    cnt = 0
    while q:
        x, y = q.popleft()
        cnt += 1
        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if nx < 0 or ny < 0 or nx >= m or ny >= n:
                continue
            if check[nx][ny] == 0 and g[x][y] & (1 << k) <= 0:
                check[nx][ny] = group
                q.append((nx, ny))
    return cnt
rooms = []               
for i in range(m):
    for j in range(n):
        if check[i][j] == 0:
            group += 1
            rooms.append(bfs(i, j, group))
            
print(group)
print(max(rooms))
ans = 0
for i in range(m):
    for j in range(n):
        for k in range(4):
            nx, ny = i + dx[k], j + dy[k]
            if nx < 0 or ny < 0 or nx >= m or ny >= n:
                continue
            if g[i][j] & (1 << k) > 0 and check[i][j] != check[nx][ny]:
                ans = max(ans, rooms[check[i][j]-1] + rooms[check[nx][ny]-1])
print(ans) 

1. 벽을 허물고 다시 bfs 하기에는 너무 시간이 오래 걸림 -> 앞에서 구한 것을 이용해서 품
2. 벽을 하나 허물면 방이 몇개 되는지 구한다
3. check 의 값을 group으로 설정 -> group을 나중에 쓰고 싶기 때문(3번을 구할 때 필요함)
4. 마지막 check[i][j] != check[nx][ny] 조건을 안넣어서 좀 헤맴
5. 비트마스크 -> i 에 따라 동서남북이 바뀌니 dx, dy 원소의 순서도 중요하다

시간 복잡도 계산