[Python/파이썬] 백준 2234번 성곽

2234번: 성곽

 

문제

대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로그램을 작성하시오.

1. 이 성에 있는 방의 개수
2. 가장 넓은 방의 넓이
3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기

위의 예에서는 방은 5개고, 가장 큰 방은 9개의 칸으로 이루어져 있으며, 위의 그림에서 화살표가 가리키는 벽을 제거하면 16인 크기의 방을 얻을 수 있다.

성은 M × N(1 ≤ M, N ≤ 50)개의 정사각형 칸으로 이루어진다. 성에는 최소 두 개의 방이 있어서, 항상 하나의 벽을 제거하여 두 방을 합치는 경우가 있다.

입력

첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다. 참고로 이진수의 각 비트를 생각하면 쉽다. 따라서 이 값은 0부터 15까지의 범위 안에 있다.

출력

첫째 줄에 1의 답을, 둘째 줄에 2의 답을, 셋째 줄에 3의 답을 출력한다.

코드

from collections import deque

n, m = map(int, input().split())
castle = []
for _ in range(m):
    castle.append(list(map(int, input().split())))
# 서 북 동 남
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]


def bfs(x, y, num):
    q = deque([(x, y)])
    room_num[x][y] = num
    cnt = 1
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if castle[x][y] & (1 << i) == 0 and room_num[nx][ny] == -1:
                q.append((nx, ny))
                room_num[nx][ny] = num
                cnt += 1
    return cnt


def find_neighbor(x, y):
    q = deque([(x, y)])
    visited = [[False]*n for _ in range(m)]
    visited[x][y] = True
    neighbor = set()
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= m or ny < 0 or ny >= n:
                continue
            if not visited[nx][ny]:
                if room_num[x][y] == room_num[nx][ny]:  # 같은 방
                    q.append((nx, ny))
                else:   # 이웃 방
                    neighbor.add(room_num[nx][ny])
                visited[nx][ny] = True
    return neighbor


room = []
room_start = []
room_num = [[-1]*n for _ in range(m)]
for i in range(m):
    for j in range(n):
        if room_num[i][j] == -1:
            room.append(bfs(i, j, len(room)))
            room_start.append([i, j])
print(len(room))
print(max(room))
remove_one = -1
for i in range(len(room)):
    r, c = room_start[i]
    for neighbor in list(find_neighbor(r, c)):
        remove_one = max(remove_one, room[neighbor]+room[i])
print(remove_one)

BFS를 이용하여 각 방의 넓이를 구해서 room에 저장해둔다.

1. q에 탐색을 시작하는 칸의 위치를 넣고 room_num에 방 번호를 넣음으로써 방문 처리를 한다.
2. q에 요소들이 존재하는 동안 아래의 과정을 반복한다
   • 현재 칸에서 4방향으로 탐색하여 아직 방문하지 않은 칸 중 같은 방에 속하는 칸이 있는지 확인한다
     같은 방에 속하려면 두 칸 사이에 벽이 없어야 한다. 이를 알아내기 위해 비트마스킹을 이용한다. 벽의 여부는 4자리 이진수로 주어지는데 왼쪽($2^3$자리)에서부터 남동북서 순서이다. 해당 자리가 1이면 벽이 존재하는 것이다. 예를 들어 11 = 0b1011이므로  남, 북, 서에 벽이 존재한다. 이것을 이용하여 우리가 원하는 방향에 벽이 있는지 &를 하여 알아본다. &한 값이 0이고 room_num에 저장된 값이 -1이라면 같은 방에 속한 칸이면서 아직 방문하지 않은 칸이므로 q에 넣어주고 room_num에 방 번호를 넣어서 방문 표시를 해준다. 그리고 cnt를 1 증가시켜준다.

이때 각 방에서 탐색을 시작한 위치도 room_start에 저장하여서 나중에 인접한 방을 파악할 때 사용한다.

 

모든 칸의 방 번호를 표시한 뒤, 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기를 알아내기 위하여 각 방이 어떤 방과 인접했는지 find_neighbor 함수를 사용한다. find_neighbor 함수는 bfs와 비슷한데 같은 방일 경우 q에 넣어주고, 다른 방인 경우 neighbor 집합에 넣어주어서 나중에 인접한 방 번호 집합인 neighbor을 리턴해준다는 점이 다르다.