해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 알고리즘 / 2234번 성곽 - BFS

www.acmicpc.net/problem/2234

문제 풀이

2234번 성곽 문제는 BFS로 풀 수 있는 문제입니다. 

성벽은 서,북,동,남 순서로 되어 있고, 벽의 정보는 각각 1,2,4,8입니다.

비트마스킹을 이용하여, 성벽의 유무를 판단하도록 합니다. 

서쪽에 벽이 없다면, 서쪽으로 이동하여 BFS 탐색을 이어나가고, 

북쪽에 벽이 없다며, 북쪽으로 이동하여 BFS 탐색을 이어나가고, 

동쪽에 벽이 없다며, 동쪽으로 이동하여 BFS 탐색을 이어나가고, 

남쪽에 벽이 없다며, 남쪽으로 이동하여 BFS 탐색을 이어나갑니다. 

해당 내용은 아래 알고리즘을 참고하시면 되고, 이 부분이 핵심 코드입니다.

		for k in range(4): # 0 - 서, 1 - 북, 2 - 동, 3 - 남
			if maps[ey][ex] & (1<<k) == 0:
				nx = dcol[k] + ex
				ny = drow[k] + ey

				if isRange(ny, nx) is False:
					break

				if visit[ny][nx] is False:
					visit[ny][nx] = True
					queue.append((ny, nx))
					r += 1

우선, 1) 이 성에 있는 방의 개수는 전체 성의 좌표를 돌면서 BFS 탐색을 호출하는 부분의 개수를 계산하여 구합니다. 

BFS 탐색을 한번 돌리면 연결되어 있는 통로는 모두 방문하게 되어, BFS 탐색을 호출하는 부분은 다른 방이 있을 때마다 호출하게 되기 때문입니다. 

2) 가장 넓은 방의 넓이는 BFS 탐색을 할 때, 반환되는 방의 크기 중 가장 큰 크기를 계산하여 구합니다. 

BFS 탐색을 할 때, 연결된 방의 좌표를 Queue에 넣을 때마다 방의 개수를 증가시키고, BFS의 탐색이 종료되면 이 방의 모든 개수를 반환하게 됩니다. 

3) 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기는 벽을 하나씩 제거해 보면서, 각 방의 크기를 구하고, 그 중 가장 큰 방을 계산하여 구합니다.

전체 코드

import sys
from collections import deque

#서, 북, 동, 남
dcol = [-1,  0, 1,  0]
drow = [0,  -1, 0,  1]

# 벽 검사
def isRange(row, col):
	if col >= w or col < 0: return False
	if row >= h or row < 0: return False
	return True

def bfs(row, col):
	queue = deque()

	#(출발점 row, 출발점 col)
	queue.append((row, col))
	visit[row][col] = True
	r = 1

	while queue:
		ey, ex = queue.popleft()
		#print("row = ", row, ",col = ", col, ", ey = ", ey , ", ex = ", ex)

		for k in range(4):
			if maps[ey][ex] & (1<<k) == 0:
				nx = dcol[k] + ex
				ny = drow[k] + ey

				if isRange(ny, nx) is False:
					break

				if visit[ny][nx] is False:
					visit[ny][nx] = True
					queue.append((ny, nx))
					r += 1
	return r


w, h = map(int, sys.stdin.readline().split())
maps = []

for i in range(h):
	line = []
	line = list(map(int, sys.stdin.readline().split()))
	maps.append(line)

# 방의 개수
room_number = 0

# 가장 넓은 방의 넓이
room_size = 0
visit = [[False]*w for _ in range(h)]

for i in range(h):
	for j in range(w):
		if visit[i][j] is False:
			room_number += 1
			room_size = max(room_size, bfs(i,j))

print(room_number)
print(room_size)

# 하나의 벽을 제거하여 l을 수 있는 가장 넓은 방의 크기
room_size_one_brick = 0
for i in range(h):
	for j in range(w):
		for k in range(4):
			if maps[i][j] & (1<<k) == (1<<k):
				visit = [[False] * w for _ in range(h)]
				maps[i][j] -= (1<<k)
				room_size_one_brick = max(room_size_one_brick, bfs(i,j))
				maps[i][j] += (1<<k)
print(room_size_one_brick)