[Python] BOJ(백준) 14502번 - 연구소

1. 링크

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

2. 난이도(solved.ac 참고)

골드5

3. 풀이

	# https://www.acmicpc.net/problem/14502
	import sys
	from itertools import permutations
	from collections import deque
	import copy
	input = sys.stdin.readline
	n, m = map(int, input().split())
	a = [list(map(int, input().split())) for _ in range(n)]
	dx = [-1, 1, 0, 0]
	dy = [0, 0, -1, 1]
	def bfs(x, y):
	temp = 0
	while q_copy:
	for _ in range(len(q_copy)):
	pop_x, pop_y = q_copy.popleft()
	for i in range(4):
	nx = pop_x + dx[i]
	ny = pop_y + dy[i]
	if 0 <= nx < n and 0 <= ny < m and a_copy[nx][ny] == 0:
	a_copy[nx][ny] = 2
	q_copy.append([nx, ny])
	for i in a_copy:
	if i.count(0) != 0:
	temp += i.count(0)
	return temp
	candidate = []
	result_list = []
	temp = []
	q = deque()
	for i in range(n):
	for j in range(m):
	if a[i][j] == 0:
	candidate.append((i, j))
	elif a[i][j] == 2:
	q.append([i, j])
	max_result = 0
	for e in permutations(candidate, 3):
	q_copy = copy.deepcopy(q)
	a_copy = copy.deepcopy(a)
	for w in e:
	a_copy[w[0]][w[1]] = 1
	result = bfs(m, n)
	if result > max_result:
	max_result = result
	print(max_result)

view raw 연구소.py hosted with ❤ by GitHub

1. input값으로 받은 a 리스트를 돌면서 값이 0이라면 전부 candidate라는 리스트에 인덱스 형태로 넣어주고(ex. (0, 1)), 2라면 큐에 담는다.

2. candidate 리스트에서 3개를 뽑아내는 순열 반복을 하면서 큐와 a를 각각 카피해서 새로운 변수에 지정해주고 그 순열에 해당하는 부분에 대해 a_copy 내의 해당 인덱스의 값을 1로 바꿔준다. (3개를 뽑아 벽을 세우는 것)

3. 그다음 result라는 변수에 bfs 함수의 리턴값을 부여한다.

3-1. bfs 함수에서는 a_copy 내의 값이 0일 경우 전부 2로 바꿔준 뒤 큐가 비게 되면 while문이 끝나면서 a_copy에서의 0의 개수 temp를 리턴한다.

4. max_result라는 변수를 부여한 뒤 매번 bfs 함수를 돌 때마다 더 큰 값으로 업데이트 되게끔 하고 그 값을 출력해서 마무리한다.

 

PyPy로는 통과했으나 Python 3으로는 시간초과가 떴다. 다시 한 번 봐야되겠지만 일단 논리는 맞았으므로 포스팅한다.