[Python] 17142. 연구소 3

www.acmicpc.net/problem/17142

17142번: 연구소 3

---

아무리 수정해도 계속 시간초과 됨 ㅠㅠ 다음에 재도전

 

메모리 (제한: MB)

0 KB

시간 (제한: 초)

0 ms

결과

시간초과

import itertools

def bfs(_lst,_dist):
​​​​global n,answer,vacumm
​​​​lst = list(_lst)
​​​​cnt = 0
​​​​infected = 0

​​​​for i in range(len(lst)):
​​​​​​​​_dist[lst[i][0]][lst[i][1]] = 0

​​​​while True:
​​​​​​​​if vacumm == infected:
​​​​​​​​​​​​answer = min(answer, cnt)
​​​​​​​​​​​​break
​​​​​​​​tmp = []
​​​​​​​​while lst:
​​​​​​​​​​​​curr_y, curr_x = lst.pop(0)
​​​​​​​​​​​​for i in range(4):
​​​​​​​​​​​​​​​​next_y = curr_y + dydx[i][0]
​​​​​​​​​​​​​​​​next_x = curr_x + dydx[i][1]
​​​​​​​​​​​​​​​​if 0 <= next_y < n and 0 <= next_x < n and MAP[next_y][next_x] != 1 and _dist[next_y][next_x] == -1:
​​​​​​​​​​​​​​​​​​​​if MAP[next_y][next_x] == 0:
​​​​​​​​​​​​​​​​​​​​​​​​_dist[next_y][next_x] = _dist[curr_y][curr_x] + 1
​​​​​​​​​​​​​​​​​​​​​​​​infected += 1
​​​​​​​​​​​​​​​​​​​​elif MAP[next_y][next_x] == 2:
​​​​​​​​​​​​​​​​​​​​​​​​_dist[next_y][next_x] = 0
​​​​​​​​​​​​​​​​​​​​else:
​​​​​​​​​​​​​​​​​​​​​​​​continue
​​​​​​​​​​​​​​​​​​​​tmp.append((next_y, next_x))
​​​​​​​​cnt += 1
​​​​​​​​lst = tmp.copy()
​​​​​​​​if not lst:
​​​​​​​​​​​​break

n, m = map(int, input().split())
MAP = [list(map(int, input().split())) for _ in range(n)]

dydx = ((-1, 0), (0, 1), (1, 0), (0, -1))
virus = []
vacumm = 0

# initialize
for r in range(n):
​​​​for c in range(n):
​​​​​​​​if MAP[r][c] == 2:
​​​​​​​​​​​​virus.append((r,c))
​​​​​​​​elif MAP[r][c] == 1:
​​​​​​​​​​​​pass
​​​​​​​​else:
​​​​​​​​​​​​vacumm += 1

perm = list(itertools.permutations(virus,m))
answer = 10 ** 10

for p in perm:
​​​​_dist = [[-1] * n for _ in range(n)]
​​​​bfs(p,_dist)

if answer == 10 ** 10:
​​​​answer = -1
print(answer)

 

문제를 푸는데 도움이 된 테스트 케이스

# Input 4 2 0 1 1 0 2 1 1 2 2 1 1 2 0 1 1 0 # Output 2