[백준] 성곽

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

2234번: 성곽

비트연산과 BFS를 같이 활용하는 문제입니다. 각 칸을 기준으로 BFS를 통해 탐색하는 과정에서 현재 칸에서 다음 칸으로 이동할 때 해당 방향에 벽이 있는지 여부를 체크해줘야하는데 이를 비트연산을 통해 체크해주면 됩니다. 벽 하나를 허물어서 얻을 수 있는 최대 방의 크기는 BFS를 통해 탐색하면서 방의 번호를 메기고 각 칸을 탐색할 때 사방탐색을 하면서 방의 번호가 다른 경우를 만나면 두 방은 합칠 수 있으므로 합쳤을 때 방의 크기를 얻을 수 있습니다.

 

import sys
from collections import deque

sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

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

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


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

# 방의 개수
group = 1

size = [-1]

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

def inRange(y, x):
    return 0 <= y < m and 0 <= x < n

def bfs(startY, startX):
    visited[startY][startX] = group

    q = deque([(startY, startX)])

    cnt = 0

    while q:
        y, x = q.popleft()

        cnt += 1

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]

            # 벽이 없는 경우에만 해당 방향으로 진행한다.
            if inRange(ny, nx) and ((1 << i) & board[y][x]) == 0 and visited[ny][nx] == 0:
                visited[ny][nx] = group
                q.append((ny, nx))

    return cnt

# 최대방의 크기
maxSize = 0

for i in range(m):
    for j in range(n):
        if not visited[i][j]:
            ret = bfs(i, j)

            maxSize = max(ret, maxSize)
            group += 1
            size.append(ret)

print(group - 1)
print(maxSize)

maxSize = 0

# 옆방과 합쳐졌을 때 최대값을 구하는 과정
# 현재 칸을 기준으로 사방탐색하여 서로 다른방이면 크기를 합쳐본다.
for i in range(m):
    for j in range(n):
        for k in range(4):
            ni = i + dy[k]
            nj = j + dx[k]

            if inRange(ni, nj) and visited[i][j] != visited[ni][nj]:
                maxSize = max(maxSize, size[visited[i][j]] + size[visited[ni][nj]])

print(maxSize)