[Python] 백준 2234 성곽

1. 문제 링크

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

2234번: 성곽

---

2. 문제 요약

1. 방의 개수 구하기
2. 가장 넓은 방 구하기
3. 하나의 벽 제거 시 가장 넓은 방 크기 구하기

---

3. 아이디어 정리

• bfs를 이용하여 탐색을 한다.

1. 방문 안 한 방 중 상하좌우 탐색하여 벽을 찾는다.
2. 벽이 존재하는 경우 "3. 하나의 벽 제거 시 가장 넓은 방 크기 구하기"를 구하기 위해 근처 벽 변수에 넣어준다.
3. 벽이 존재하지 않는 경우 현재 방의 크기를 늘려주고 deque에 넣어준다.
4. 현재 그래프에서 bfs 탐색이 끝나면 가장 넓은 방의 넓이를 갱신하고, dict로 된 room_num[방 번호] = 방 크기 저장한다.
5. 근처 벽 변수로 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기 구한다.

---

4. 문제 풀이

4-1. 내 풀이

import sys
from collections import deque
from collections import defaultdict

def find_imposs(num):
    """
    벽 찾기
    """
    list_ = list()
    if num >= 8:
        num -= 8
        list_.append(1)
    if num >= 4:
        num -= 4
        list_.append(3)
    if num >= 2:
        num -= 2
        list_.append(0)
    if num >= 1:
        num -= 2
        list_.append(2)
    return list_

# 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

n, m = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]
graph_num = [[-1] * n for _ in range(m)]  # 방 번호 저장
room_num = defaultdict(int)               # 방마다 총 넓이 저장
near_room = set()                         # 주변 방 저장

count = 0     # 이 성에 있는 방의 개수
max_room = 0  # 가장 넓은 방의 넓이

for i in range(m):
    for j in range(n):
        if graph_num[i][j] == -1:   # 방문하지 않은 경우 탐색
            dq = deque([(i, j)])
            count += 1
            graph_num[i][j] = count
            num = 1    # 해당 방의 넓이
            while dq:
                x, y = dq.popleft()
                imposs = find_imposs(graph[x][y])   # 상하좌우 중 벽 리스트 얻기
                for d in range(4):
                    nx = x + dx[d]
                    ny = y + dy[d]
                    if nx < 0 or ny < 0 or nx >= m or ny >= n:
                        continue
                    if d in imposs and graph_num[nx][ny] != -1: # 벽이고, 주변 벽에 번호가 존재하는 경우, 주변 벽리스트에 저장
                        if graph_num[nx][ny] != count:
                            near_room.add((count, graph_num[nx][ny]))
                    if d in imposs or graph_num[nx][ny] != -1:  # 벽이거나 방문을 한 경우 그만
                        continue
                    graph_num[nx][ny] = count
                    dq.append((nx, ny))
                    num += 1     # 총 방의 수 세기
            max_room = max(max_room, num)     # 가장 넓은 방의 넓이 구하기
            room_num[count] = num             # 각 방별 크기 저장

# 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기 구하기
max_two_room = 0
for x, y in near_room:
    max_two_room = max(max_two_room, room_num[x] + room_num[y])

print(count)
print(max_room)
print(max_two_room)

 

---

5. 결론

• 섬의 수 구하기 문제와 비슷하다. 그러나 벽을 직접 처리&벽을 제거하여 가장 넓은 방 구하기 처리를 해야한다.
• bfs 응용문제