이번 문제는 비트마스킹과 BFS를 통해 해결하였다. 각 좌표별로 벽이 있는 정보를 입력받고, BFS를 통해 탐색하며 벽의 유무를 비트마스킹으로 판별하여 방의 정보를 저장하였다. cnt리스트에는 각 방의 크기를 저장하였고, rooms리스트에는 각 방의 번호를 부여하여 저장하였다. 탐색이 끝나면 모든 좌표를 순회하며 현재 좌표의 4방향에 대하여 방 번호가 다르다면, 두 방의 크기의 합을 구하여 그 중에서 최댓값을 결과변수로 취하도록 하여 해결하였다.

Code

from collections import deque
n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(m)]
cnt = [[0 for _ in range(n)] for _ in range(m)]
rooms = [[0 for _ in range(n)] for _ in range(m)]
dy, dx = [0, -1, 0, 1], [-1, 0, 1, 0]
room_cnt = 0
largest_room = 0
answer = 0
def get_room(sy, sx):
    q = deque()
    q.append((sy, sx))
    path = [(sy, sx)]
    rooms[sy][sx] = room_cnt
    result = 1
    while q:
        y, x = q.popleft()
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < m and 0 <= nx < n and not rooms[ny][nx]:
                if not grid[y][x] & (1<<i):
                    q.append((ny, nx))
                    path.append((ny, nx))
                    rooms[ny][nx] = room_cnt
                    result += 1
    for y, x in path:
        cnt[y][x] = result
for i in range(m):
    for j in range(n):
        if not rooms[i][j]:
            room_cnt += 1
            get_room(i, j)
for i in range(m):
    for j in range(n):
        for d in range(4):
            ni, nj = i+dy[d], j+dx[d]
            if 0 <= ni < m and 0 <= nj < n:
                if rooms[i][j] != rooms[ni][nj]:
                    answer = max(answer, cnt[i][j]+cnt[ni][nj])
        if largest_room < cnt[i][j]:
            largest_room = cnt[i][j]
print(room_cnt)
print(largest_room)
print(answer)