gold 3 / 그래프 이론, 그래프 탐색, 너비 우선 탐색, 비트마스킹
문제 흐름
일단 친절하게 지도 그림도 첨부되어있기도 했고, 문제 읽고나니 확실히 bfs구나 했다.
이 문제에서 출력해야하는 답안은 3개이다.
- 이 성에 있는 방의 개수
- 가장 넓은 방의 넓이
- 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기
방의 개수와 넓이는 bfs로 돌면서 체크하면 되기 때문에 간단했다.
조금 독특한 포인트라고 한다면 현재 위치에서 탐색 가능한 방향이 2진수로(?) 주어진다는 점이다. (완전히 2진수는 아니지만..)
보통은 1과 0으로 벽과 길을 만들어 주어지는 문제를 풀었어서 신선했다.
벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다. 참고로 이진수의 각 비트를 생각하면 쉽다. 따라서 이 값은 0부터 15까지의 범위 안에 있다.
일단 💡 bitwise 연산을 통해 탐색 가능 방향을 읽는 기능이 필요하다고 생각했다.
평범하게 0b0001, 0b0010, 0b0100, 0b1000과 and 연산을 한 결과를 확인하고, 네 방향의 진행 가능 여부를 반환하면 되겠다.
해당 기능은 walls라는 함수로 구현했다.
이런 방식을 비트마스킹 알고리즘 이라고 한다는 걸 처음 알았다.
탐색 가능 방향을 읽는 기능을 구현했으니 다음은 정석 💡 bfs를 통해 성을 탐색하는 기능이 필요하겠다.
탐색 순서, 인접 방 등을 어떻게 연결지을지는 나중에 생각하고 결국 bfs는 필요하므로 bfs라는 함수로 구현했다.
이제 가장 고민했던 부분인데.. 인접한 방을 어떻게 찾을것인가? 이다.
인접한 방을 찾을 필요는 없었지만, 예전에 한참 백준 문제를 많이 풀 때 이와 비슷하게 쪼개진 여러 부분을 모두 탐색해야하는 문제를 푼 기억이 났다.
bfs를 진행할 때 현 위치에서 벽 으로 막혀 못가는 칸을 체크해서 같이 반환하는 것이다.
같은 방 안에서도 벽으로 막힌 뒷편을 체크해 넘기게되긴 하지만, 이는 bfs를 실행시키는 함수에서 처리하기로 했다.
그럼 마지막으로 필요한 기능은 💡 인접한 다른 방들에 대해 차례로 bfs를 실행시키는 기능이다.
여기서도 큐를 이용했는데 뼈대로 생각한 내용은 bfs와 비슷했다.
세부적으로는 방 내부를 탐색하지만 넓게 보면 성에 있는 방들을 탐색하는 것과 비슷하다고 생각하면 된다.
아까 bfs에서 같이 체크해서 받은 벽으로 막혀 못가는 칸을 차례로 확인하면서 현재 방이라면 pass, 다른 번호의 방이라면 인접한 방이라는 의미이므로 그 방의 크기와 현재 방의 크기를 더한 값이 클 경우 업데이트하도록 했다.
말로 풀으니 더 어렵게 느껴지는데 코드를 보는게 이해가 더 빠를 것 같다.
코드
import sys
from collections import deque
from pprint import pprint
input = sys.stdin.readline
# bfs
def walls (location: int):
result = []
if location&0b0001 == 2**0: # The west
result.append(False) # Wall
else:
result.append(True) # No wall
if location&0b0010 == 2**1: # The north
result.append(False) # Wall
else:
result.append(True) # No wall
if location&0b0100 == 2**2: # The east
result.append(False) # Wall
else:
result.append(True) # No wall
if location&0b1000 == 2**3: # The south
result.append(False) # Wall
else:
result.append(True) # No wall
return result
def bfs (Map: list, visit: list, sx: int, sy: int, room_number: int):
q = deque([(sx, sy)])
visit[sx][sy] = room_number
size = 1
over_the_wall = []
dir_x = [ 0,-1, 0, 1]
dir_y = [-1, 0, 1, 0]
while q:
x, y = q.popleft()
for i, go in enumerate(walls(Map[x][y])):
nx = x + dir_x[i]
ny = y + dir_y[i]
if nx<0 or ny<0 or nx>=len(Map) or ny>=len(Map[0]):
continue
if go != True:
over_the_wall.append((nx, ny))
continue
if not visit[nx][ny]:
q.append((nx, ny))
visit[nx][ny] = room_number
size += 1
return size, over_the_wall
def castle (Map: list, visit: list, N: int, M: int):
room_number = 1
room_size = {}
sx, sy = 0, 0
q = deque([(0, sx, sy)])
max_size = 0
max_sum_size = 0
while q:
conn_size, x, y = q.popleft()
if visit[x][y]:
continue
size, otw = bfs(Map, visit, x, y, room_number)
room_size[room_number] = size
max_size = max(max_size, size)
max_sum_size = max(max_sum_size, size+conn_size)
# print(f"room_number{room_number}, size: {size}, max size: {max_sum_size}")
# pprint(visit)
for px, py in otw:
if visit[px][py] == room_number:
continue
elif visit[px][py] == 0:
q.append((size, px, py))
else:
max_sum_size = max(max_sum_size, size+room_size[visit[px][py]])
room_number += 1
print(room_number-1)
print(max_size)
print(max_sum_size)
if __name__ == "__main__":
N, M = map(int, input().split())
Map = [list(map(int, input().split())) for _ in range(M)]
visit = [[0 for i in range(N)] for j in range(M)]
castle(Map, visit, N, M)마무리
역시 bfs도 오랜만이다.
그래도 따로 찾아보지 않고 다시 구현해냈다는 점에 의미가 좀 있는 것 같다.
전에도 bfs 참 좋아했었는데 그래도 기억하긴 하는구나..!
인접한 방을 찾는 부분을 정말 정말 많이 고민했다.
room_number, room_size, max_size, max_sum_size 등 변수가 너무 많아지는 것 같아서 걱정도 됐고, 일단 성공하긴 했지만 지금 사용한 방식 자체도 썩 효율적이지는 않아보인다. 🥲
다른 사람들 풀이도 읽어봐야겠다.
