[Python] 백준 14502. 연구소

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

14502번: 연구소

연구소 3과 접근방법은 동일하다. combinations을 사용할 대상이 '벽 3개'로 바뀐 것일 뿐.

BFS에서의 특이점이라면, BFS에서 탐색할 연구소 지도는 복사본을 사용해야 한다.

원본 map에서 3개의 기둥을 선택한 뒤 BFS로 탐구하고, 다시 원본 map에서 다른 3개의 기둥을 선택해야 하기 때문.

 

 

 

	import sys
	from copy import deepcopy
	from itertools import combinations
	from collections import deque
	n, m = map(int, sys.stdin.readline().split())
	maps, empty_wall, virus = [], [], []
	dirs = [(0,1),(1,0),(-1,0),(0,-1)]
	for y in range(n):
	tmp = list(map(int, sys.stdin.readline().split()))
	for x in range(m):
	# 기둥의 좌표 저장
	if tmp[x] == 0:
	empty_wall.append((y, x))
	elif tmp[x] == 2:
	# 바이러스의 좌표 저장
	virus.append((y, x))
	# 원본 maps 저장
	maps.append(tmp)
	def count_zero(maps):
	count = 0
	for y in range(len(maps)):
	for x in range(len(maps[0])):
	if maps[y][x] == 0:
	count += 1
	return count
	def bfs(start, candidate, maps):
	# 원본 map을 보존한 채 BFS 순회를 해야 함
	maps = deepcopy(maps)
	# 기둥을 세우기로 선택한 좌표를 반영한다
	for y, x in candidate:
	maps[y][x] = 1
	queue = deque()
	queue.extend(start)
	while queue:
	y, x = queue.popleft()
	for dy, dx in dirs:
	ny, nx = y+dy, x+dx
	if 0 <= ny < len(maps) and 0 <= nx < len(maps[0]) and maps[ny][nx] == 0:
	maps[ny][nx] = 2
	queue.append((ny, nx))
	return count_zero(maps)
	# 빈 곳에 기둥을 세우기 위한 경우의 수
	candidates = list(combinations(empty_wall, 3))
	max_value = 0
	for i in candidates:
	result = bfs(virus, list(i), maps)
	if max_value < result:
	max_value = result
	print(max_value)

view raw [백준] 연구소.py hosted with ❤ by GitHub