[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