[백준] 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의 답을 출력한다.

주의할 점

1. 벽이 동, 서, 남, 북에 있을 수도 있다..! 즉, 없을 수도 있다. 없으면 해당 위치의 값은 0
2. 주어진 예제외에 다음 예제로 테스트해보기. (저는 이 예제를 통해 keyError, 틀리게 구현한 것 다 잡았습니다..)

예제:
7 5
3 6 3 2 6 3 6
1 12 9 8 12 1 4
13 3 2 6 15 9 12
3 0 0 4 7 11 6
9 8 8 12 9 14 13

정답:
7
11
17

제출 코드

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

st_walls = (1, 2, 4, 8)
# 위치마다 쓰여진 벽의 합 값을 key로 두고 동, 서, 남, 북 중 어느 벽이 세워져있는 지를 value로 둠. (동서남북 4가지 경우라 16가지 밖에 안되어서 직접 작성함)
walls = {0: [], 1: [1], 2: [2], 3: (1, 2), 4: [4], 5: (1, 4), 6: (2, 4), 7: (1, 2, 4), 8: [8], 9: (1, 8), 10: (2, 8), 11: (1, 2, 8), 12: (4, 8), 13: (1, 4, 8), 14: (2, 4, 8), 15: (1, 2, 4, 8)}
# 현 위치에서 동쪽 벽이 없으면 동쪽 벽쪽에 있는 위치에 서쪽 벽이 없어야 함.
opposite_walls = {1: 4, 2: 8, 4: 1, 8: 2}

n, m = map(int, input().split())
m_ap = [list(map(int, input().split())) for _ in range(m)]
visited = [[-1] * n for _ in range(m)]

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

def bfs(_x, _y, a):
    q = deque()
    q.append([1, _x, _y])
    visited[_x][_y] = a
    result = 0
    while q:
        move, _x, _y = q.popleft()
       
        for sw in st_walls:
            if sw in walls[m_ap[_x][_y]]:continue
            x = _x
            y = _y
          
            if sw == 1:
                x += dx[0]
                y += dy[0]
            elif sw == 2:
                x += dx[1]
                y += dy[1]
            elif sw == 4:
                x += dx[2]
                y += dy[2]
            else:
                x += dx[3]
                y += dy[3]
            if x < 0 or y < 0 or x >= m or y >= n: continue
            if opposite_walls[sw] in walls[m_ap[x][y]]: continue
            if visited[x][y] != -1: continue
              
            visited[x][y] = a
            q.append([move + 1, x, y])
  

cnt = 0
r_esult = dict()
# 이 성에 있는 방의 개수
for i in range(m):
    for j in range(n):
        if visited[i][j] == -1:
            bfs(i, j, cnt) 
            cnt += 1
print(cnt)

# 가장 넓은 방의 넓이
for c in range(cnt):
    r_esult[c] = 0
    for i in range(m):
        for j in range(n):
            if c == visited[i][j]:
                r_esult[c] += 1
print(max(r_esult.values()))
# 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기
re_sult = 0

for i in range(m):
    for j in range(n):
     	# 동서남북에 있는 모든 벽을 허물어봄. (이미 같은 방이면 continue)
        for k in range(4):
            x = i + dx[k]
            y = j + dy[k]
         
            if x < 0 or y < 0 or x >= m or y >= n: continue
            if visited[i][j] == visited[x][y]: continue
            re_sult = max(re_sult, r_esult[visited[i][j]] + r_esult[visited[x][y]])

print(re_sult)