https://acmicpc.net/problem/2234

풀이

#bfs
1. bfs를 이용해서 방의 최대 넓이와 개수를 구했다.
2. 벽의 정보가 이진수의 합으로 주어지기 때문에 [8, 4, 2, 1] 순서로 (dx, dy도 이 방향에 맞춰서 선언) 벽의 정보를 확인해주면서 벽이 없는 경우에 탐색을 진행했다. 남아있는 벽의 값이 이번 차례의 이진수보다 크거나 같으면 벽이 있는 것으로 벽이 있으면 그만큼 빼주면서 계산해줬다. (ex. 11->3->1)
3. 벽을 하나 없앴을 때 최대 넓이를 구하기 위한 정보로 bfs 탐색이 끝나기 전에 room_info에 각 위치에 방 번호와 이 방의 넓이를 넣어줬다.
4. 벽을 하나 없앴을 때 최대 넓이를 구하기 위해 완전탐색으로 삼중반복문을 사용해 없앨 벽을 정해주고, 없앤 방향으로 나아갈 수 있는 경우에 지금 위치와 다음 위치가 속했던 방이 서로 다른 방이었다면 두 값을 더해서 최대값을 갱신한다.

코드

from collections import deque
import copy

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(M)]
temp_arr = copy.deepcopy(arr)

binary = [8, 4, 2, 1] # 남, 동, 북, 서

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

count = 0 # 방의 개수
visited = [[0] * N for _ in range(M)]
room_info = [[[] for _ in range(N)] for _ in range(N)]

group_num = 0


def bfs(x, y):
    global group_num

    visited[x][y] = 1

    q = deque()
    q.append((x,y))

    area = 1 # 이 방 넓이

    # 이 방에 속하는 칸 담기 위한 배열
    group = []
    group.append((x,y))

    while q:
        px, py = q.popleft()
        wall = arr[px][py]
        for i in range(4):
            # 벽 있음 -> 못 감
            if wall >= binary[i]:
                wall -= binary[i]
            # 벽이 없고 / 다음 범위가 유효하면서 방문하지 않은 경우
            else:
                nx, ny = px+dx[i], py+dy[i]

                if 0<=nx<M and 0<=ny<N and not visited[nx][ny]:
                    area += 1
                    q.append((nx,ny))
                    visited[nx][ny] = 1
                    group.append((nx, ny))

    # 각 칸에 대해 방의 정보 담기(방번호, 방의 넓이)
    for i, j in group:
        room_info[i][j].append(group_num)
        room_info[i][j].append(area)

    group_num+=1
    return area

# 원래 방 상태에서 최대 방 넓이, 방 개수 구하기
max_area = 0

for i in range(M):
    for j in range(N):
        if not visited[i][j]:
            max_area = max(bfs(i, j), max_area)
            count += 1

# 벽을 하나 없앴을 때 최대 방 넓이 구하기
maybe_max = 0
for i in range(M):
    for j in range(N):
        for d in range(4):
            if arr[i][j] >= binary[d]:
                nx, ny = i+dx[d], j+dy[d]

                if 0<=nx<M and 0<=ny<N:
                    # 방 종류가 다른 경우에 방 넓이 합치기
                    if room_info[i][j][0] != room_info[nx][ny][0]:
                        #print(room_info[i][j])
                        maybe_max = max(maybe_max, room_info[i][j][1]+room_info[nx][ny][1])


print(count)
print(max_area)
print(maybe_max)