[백준 2234] 성곽(Python)

1. 요약

성곽의 크기와 벽이 주어졌을 때, 이 성에 있는 방의 개수, 가장 넓은 방의 넓이, 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기를 구해야한다. 벽은 통과할 수 없다. 서쪽 벽은 1, 동쪽벽은 4, 북쪽 벽은 2, 남쪽 벽은 8이며, 벽에 대한 정보는 벽이 가리키는 숫자 또는 숫자들의 합으로 주어진다.

2. 아이디어

임의의 좌표 y,x에 대해 (y,x)칸이 가리키는 벽의 정보를 딕셔너리의 key로 설정하고, 갈 수 있는 방향들을 value로 설정한다.

방의 개수를 구하기 위해 성곽을 탐색하면서 처음 방문하는 곳이면 방의 개수를 하나 증가시키고 bfs 탐색을 실시한다.

가장 넓은 방의 넓이를 구하기 위해 bfs하여 나온 방의 넓이를 비교하며 가장 큰 값을 찾는다.

하나의 벽을 제거하여 가장 넓은 방의 크기를 구하기 위해, 1개의 벽을 제거할 수 있는 모든 경우의 대해 bfs를 실시하고 이 중 가장 넓이가 큰 방을 구하면 된다. 이것이 가능한 이유가 시간제한이 2초이고, 성곽의 최대 크기가 50x50이다. 게다가 위에서 구해야하는 2개의 답을 한 번의 bfs로 구할 수 있기 때문이다.

3. 코드

import sys
from itertools import combinations
from collections import deque

c, r = map(int, sys.stdin.readline().rsplit())
castle = [list(map(int, sys.stdin.readline().rsplit())) for _ in range(r)]

dirs = {}
dirs[0] = [[0,1],[0,-1],[1,0],[-1,0]]
for i in range(1, 5):
    for case in tuple(combinations((1,2,4,8), i)):
        v = []
        if 1 not in case: v.append([0,-1])
        if 2 not in case: v.append([-1,0])
        if 4 not in case: v.append([0,1])
        if 8 not in case: v.append([1,0])
        dirs[sum(case)] = v

def bfs(sy, sx, visited):
    q = deque()
    q.append((sy, sx))
    cnt = 1

    while q:
        y, x = q.popleft()
        num = castle[y][x]

        for dy, dx in dirs[num]:
            ny = y + dy
            nx = x + dx

            if -1<ny<r and -1<nx<c:
                if not visited[ny][nx]:
                    visited[ny][nx] = True
                    cnt += 1
                    q.append((ny,nx))
    
    return cnt

def solve12():
    visited = [[False for _ in range(c)] for _ in range(r)]
    ans1 = 0
    ans2 = 0
    for i in range(r):
        for j in range(c):
            if not visited[i][j]:
                visited[i][j] = True
                ans1 += 1
                total = bfs(i,j,visited)
                if ans2 < total: ans2 = total
                
    return '\n'.join((str(ans1), str(ans2)))

def solve3():
    ans = 0
    for i in range(r):
        for j in range(c):
            num = castle[i][j]
            for k in (1,2,4,8):
                if num - k < 0: break
                _num = num - k
                castle[i][j] = _num
                visited = [[False for _ in range(c)] for _ in range(r)]
                for y in range(r):
                    for x in range(c):
                        if not visited[y][x]:
                            visited[y][x] = True
                            total = bfs(y, x, visited)
                            if ans < total: ans = total

                castle[i][j] = num

    return ans

print(solve12())
print(solve3())