2234번: 성곽
첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를,
www.acmicpc.net
문제
대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로그램을 작성하시오.
- 이 성에 있는 방의 개수
- 가장 넓은 방의 넓이
- 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기
위의 예에서는 방은 5개고, 가장 큰 방은 9개의 칸으로 이루어져 있으며, 위의 그림에서 화살표가 가리키는 벽을 제거하면 16인 크기의 방을 얻을 수 있다.
성은 M × N(1 ≤ M, N ≤ 50)개의 정사각형 칸으로 이루어진다. 성에는 최소 두 개의 방이 있어서, 항상 하나의 벽을 제거하여 두 방을 합치는 경우가 있다.
입력
첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다. 참고로 이진수의 각 비트를 생각하면 쉽다. 따라서 이 값은 0부터 15까지의 범위 안에 있다.
출력
첫째 줄에 1의 답을, 둘째 줄에 2의 답을, 셋째 줄에 3의 답을 출력한다.
코드
from collections import deque
n, m = map(int, input().split())
castle = []
for _ in range(m):
castle.append(list(map(int, input().split())))
# 서 북 동 남
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]
def bfs(x, y, num):
q = deque([(x, y)])
room_num[x][y] = num
cnt = 1
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if castle[x][y] & (1 << i) == 0 and room_num[nx][ny] == -1:
q.append((nx, ny))
room_num[nx][ny] = num
cnt += 1
return cnt
def find_neighbor(x, y):
q = deque([(x, y)])
visited = [[False]*n for _ in range(m)]
visited[x][y] = True
neighbor = set()
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= m or ny < 0 or ny >= n:
continue
if not visited[nx][ny]:
if room_num[x][y] == room_num[nx][ny]: # 같은 방
q.append((nx, ny))
else: # 이웃 방
neighbor.add(room_num[nx][ny])
visited[nx][ny] = True
return neighbor
room = []
room_start = []
room_num = [[-1]*n for _ in range(m)]
for i in range(m):
for j in range(n):
if room_num[i][j] == -1:
room.append(bfs(i, j, len(room)))
room_start.append([i, j])
print(len(room))
print(max(room))
remove_one = -1
for i in range(len(room)):
r, c = room_start[i]
for neighbor in list(find_neighbor(r, c)):
remove_one = max(remove_one, room[neighbor]+room[i])
print(remove_one)
BFS를 이용하여 각 방의 넓이를 구해서 room에 저장해둔다.
- q에 탐색을 시작하는 칸의 위치를 넣고 room_num에 방 번호를 넣음으로써 방문 처리를 한다.
- q에 요소들이 존재하는 동안 아래의 과정을 반복한다
- 현재 칸에서 4방향으로 탐색하여 아직 방문하지 않은 칸 중 같은 방에 속하는 칸이 있는지 확인한다
같은 방에 속하려면 두 칸 사이에 벽이 없어야 한다. 이를 알아내기 위해 비트마스킹을 이용한다. 벽의 여부는 4자리 이진수로 주어지는데 왼쪽($2^3$자리)에서부터 남동북서 순서이다. 해당 자리가 1이면 벽이 존재하는 것이다. 예를 들어 11 = 0b1011이므로 남, 북, 서에 벽이 존재한다. 이것을 이용하여 우리가 원하는 방향에 벽이 있는지 &를 하여 알아본다. &한 값이 0이고 room_num에 저장된 값이 -1이라면 같은 방에 속한 칸이면서 아직 방문하지 않은 칸이므로 q에 넣어주고 room_num에 방 번호를 넣어서 방문 표시를 해준다. 그리고 cnt를 1 증가시켜준다.
- 현재 칸에서 4방향으로 탐색하여 아직 방문하지 않은 칸 중 같은 방에 속하는 칸이 있는지 확인한다
이때 각 방에서 탐색을 시작한 위치도 room_start에 저장하여서 나중에 인접한 방을 파악할 때 사용한다.
모든 칸의 방 번호를 표시한 뒤, 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기를 알아내기 위하여 각 방이 어떤 방과 인접했는지 find_neighbor 함수를 사용한다. find_neighbor 함수는 bfs와 비슷한데 같은 방일 경우 q에 넣어주고, 다른 방인 경우 neighbor 집합에 넣어주어서 나중에 인접한 방 번호 집합인 neighbor을 리턴해준다는 점이 다르다.
'문제풀이 > DFS_BFS' 카테고리의 다른 글
[Python/파이썬] 백준 1937번 욕심쟁이 판다 (0) | 2023.10.29 |
---|---|
[Python/파이썬] 백준 20924번 트리의 기둥과 가지 (0) | 2023.10.24 |
[Python/파이썬] 백준 13459번 구슬 탈출 (0) | 2023.10.14 |
[Python/파이썬] 백준 13913번 숨바꼭질 4 (0) | 2023.10.09 |
[Python/파이썬] 백준 1240번 노드사이의 거리 (0) | 2023.09.25 |