[백준] 2234 - 성곽 Python

https://www.acmicpc.net/problem/2234

2234번: 성곽

성의 지도를 입력받아 성에 있는 방의 개수, 가장 넓은 방의 넓이, 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기를 구하는 문제다. 벽에 대한 정보는 0 ~ 15 사이 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다. 

 

방의 개수와 가장 넓은 방의 넓이는 완전탐색, BFS 를 이용해 구할 수 있다.

- 왼쪽 위부터 방문하지 않은 지점을 시작점으로 잡아서 벽으로 막혀있지 않은 인접한 지점을 모두 방문한다.

- 시작지점은 인접한 지점들과 함께 하나의 방을 나타내기 때문에, BFS 를 돌린 횟수가 곧 방의 개수가 된다.

- 각 BFS 마다 방의 넓이를 계산해 배열에 넣어둔다.

 

BFS 에서는 인접한 지점으로 이동하기 위해, 지도를 벗어나지 않는지, 벽으로 막혀있지 않은지를 판별해야 한다.

벽은 서쪽, 북쪽, 동쪽, 남쪽 순으로 주어지기 때문에, 움직임 또한 서쪽, 북쪽, 동쪽, 남쪽으로 맞춰준다면, for 문 하나로 각각의 인접한 방향으로 이동할 수 있는지를 판별할 수 있다.

# 서쪽,북쪽,동쪽,남쪽
move = [(0, -1), (-1, 0), (0, 1), (1, 0)]

쉬프트 연산으로 각 방향으로의 비트가 1이라면 벽이 있다고 판단한다.

# i 는 0,1,2,3 중 하나
matrix[row][col] & 1 << i

이후 하나의 벽을 제거해 얻을 수 있는 가장 넓은 방의 넓이는 한 번의 반복문을 이용해 구할 수 있다. 벽을 기준으로 인접한 방의 행, 열 값을 저장해 이를 이용한다.

-  칸마다 visited 배열에, 칸이 속하는 방에 해당하는 방 배열의 인덱스값을 넣어두어 이를 바탕으로 칸에 해당하는 방의 넓이를 찾는다.

-  벽을 기준으로 양쪽 칸의 visited 값이 다르다면, 서로 다른 두 방이므로, 두 방의 넓이를 더한 값 중 가장 큰 값이다.

for row1, col1, row2, col2 in barriers:
    if visited[row1][col1] != visited[row2][col2]:
        removed = max(removed,rooms[visited[row1][col1]]+rooms[visited[row2][col2]])​

전체 코드는 아래와 같다.

from collections import deque
from sys import stdin


def bfs(row, col, cnt):
    s = 0
    queue = deque()
    queue.append((row, col))
    visited[row][col] = cnt
    while queue:
        row, col = queue.popleft()
        s += 1
        for i in range(4):
            r = row + move[i][0]
            c = col + move[i][1]
            if 0 <= r < M and 0 <= c < N and visited[r][c] == -1:
                if not matrix[row][col] & 1 << i:
                    queue.append((r, c))
                    visited[r][c] = cnt
                else:
                    barriers.append((row, col, r, c))
    return s


N, M = map(int, stdin.readline().split())
matrix = [list(map(int, stdin.readline().split())) for _ in range(M)]
visited = [[-1]*N for _ in range(M)]
move = [(0, -1), (-1, 0), (0, 1), (1, 0)]
barriers = []
rooms = []
removed = 0
cnt = 0

for i in range(M):
    for j in range(N):
        if visited[i][j] == -1:
            rooms.append(bfs(i, j, cnt))
            cnt += 1

for row1, col1, row2, col2 in barriers:
    if visited[row1][col1] != visited[row2][col2]:
        removed = max(removed,
                      rooms[visited[row1][col1]]+rooms[visited[row2][col2]])

print(f"{cnt}\n{max(rooms)}\n{removed}")