[백준 2234번] 성곽

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

import sys
from collections import deque
input = sys.stdin.readline

# 서 : 1
# 북 : 2
# 동 : 4
# 남 : 8

# 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로

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

# 성에는 최소 두 개의 방이 있어서, 항상 하나의 벽을 제거하여 두 방을 합치는 경우가 있다.

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

n, m = map(int,input().split())

visited = [[False]*n for _ in range(m)]

area = [list(map(int,input().split())) for _ in range(m)]

answer = []

maximum = float("-inf")

def get_block_info(n):

    return list(bin(n).split('0b')[1][::-1].ljust(4,'0'))

def bfs(x,y):

    if visited[x][y]:
        return -1
    
    visited[x][y] = True

    q = deque([(x,y)])

    count = 0

    while q:
        
        cx, cy = q.popleft()

        count += 1

        if 0 <= cx-1 < m and not visited[cx-1][cy] and get_block_info(area[cx][cy])[1] == '0':
            q.append((cx-1,cy))
            visited[cx-1][cy] = True
        if 0 <= cx+1 < m and not visited[cx+1][cy] and get_block_info(area[cx][cy])[3] == '0':
            q.append((cx+1,cy))
            visited[cx+1][cy] = True
        if 0 <= cy-1 < n and not visited[cx][cy-1] and get_block_info(area[cx][cy])[0] == '0':
            q.append((cx,cy-1)) 
            visited[cx][cy-1] = True
        if 0 <= cy+1 < n and not visited[cx][cy+1] and get_block_info(area[cx][cy])[2] == '0':
            q.append((cx,cy+1))
            visited[cx][cy+1] = True

    return count

for i in range(m):
    for j in range(n):
        result = bfs(i,j)
        
        if result != -1:
            answer.append(result)

for i in range(m):
    for j in range(n):
        block_info = get_block_info(area[i][j])

        if block_info[0] == '1':
            visited = [[False]*n for _ in range(m)]
            area[i][j] -= 1
            maximum = max(maximum,bfs(i,j))
            area[i][j] += 1

        if block_info[1] == '1':
            visited = [[False]*n for _ in range(m)]
            area[i][j] -= 2
            maximum = max(maximum,bfs(i,j))
            area[i][j] += 2 

        if block_info[2] == '1':
            visited = [[False]*n for _ in range(m)]
            area[i][j] -= 4
            maximum = max(maximum,bfs(i,j))
            area[i][j] += 4
 
        if block_info[3] == '1':
            visited = [[False]*n for _ in range(m)]
            area[i][j] -= 8
            maximum = max(maximum,bfs(i,j))
            area[i][j] += 8

print(len(answer))
print(max(answer))
print(maximum)

 

이번 문제는 M x N 크기의 영역에 상하좌우에 존재하는 벽에 대한 정수들이 담겨있을 때 '벽으로 둘러싸인 방의 개수'와 '가장 넓은 방의 넓이', 그리고 '하나의 벽을 제거하여 얻을 수 있는 방 넓이의 최댓값'을 구하는 문제이다.

 

 먼저 상하좌우로 이동할 수 있는지 여부를 판단하기 위해 주어진 숫자를 2진수화하는 함수(get_block_info)를 구현하였다. 그리고 각 방의 넓이와 개수를 구하기 위해 BFS 함수를 구현하였다.

 

마지막으로 구해야하는 하나의 벽을 제거하여 얻을 수 있는 방의 크기는 이전에 풀었던 '벽 부수고 이동하기'와 같이 3차원 배열로 만들어야 하는줄 알고 헤맸었는데, M과 N의 크기가 작기 때문에 완전탐색으로 풀이해도 시간초과 없이 풀이가 가능하다.

 

따라서 모든 좌표에서 상하좌우에 벽이 있는지 확인하고, 벽이 있다면 해당 벽을 제거한 뒤에 BFS를 실행해주고 다시 원상복구 시켜주는 방식으로 완전탐색하였다.

 

BFS와 비트마스킹, 완전탐색을 연습해볼 수 있었던 좋은 문제였다 :)