[BOJ] 17141. 연구소2 Python

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

17141번: 연구소 2

 

 

1. 해결방법

어우 완전탐색 문제이다.

완전탐색을 하드코딩으로 푸니까 중간에 로직이 꼬여서 고생을 좀 했다.

이 문제도 연구소1처럼 시간초과를 생각하면서 코드를 짜야한다.
본인은  바이러스가 놓일 수 있는 위치를 미리 리스트에 담아두어서 백트래킹으로 놓일 수 있는 경우의 수를 모두 탐색하였다. (Combinations을 사용해도 됨)

1. 미리 바이러스가 놓일 위치를 리스트에 담는다.
2. dfs (백트래킹)을 이용해서 리스트에 담은 바이러스 리스트의 방문체크를 하면서 놓일 경우의 수를 재귀로 돌린다.
3. 재귀를 돌면서 바이러스 놓인 수가 M과 같다면 BFS를 돌린다.
4. BFS를 통해 cnt 값을 갱신한다.

 

 

2. 정답코드

import sys
from itertools import combinations
from collections import deque
from copy import deepcopy
input = sys.stdin.readline

N, M = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(N)]
dy, dx = (1, -1, 0, 0), (0, 0, 1, -1)

virus = []
for i in range(N):
    for j in range(N):
        if maps[i][j] == 2:
            virus.append((i, j))

len_virus = len(virus)
chk = [False] * len_virus

# 바이러스 확산
def bfs(new_maps):
    global min_v, zero

    q = deque(virus_list)

    while q:
        ey, ex, cnt = q.popleft()

        for d in range(4):
            ny, nx = ey + dy[d], ex + dx[d]
            if 0 <= ny  < N and 0 <= nx < N:
                if new_maps[ny][nx] == 0 or new_maps[ny][nx] == 2:
                    new_maps[ny][nx] = 3
                    q.append((ny, nx, cnt + 1))

    for i in range(N):
        for j in range(N):
            if new_maps[i][j] == 0:
                return 1e9
    else:
        return cnt
    return cnt


# 바이러스 백트래킹
def dfs(idx, depth):
    global answer, min_v

    # 종료 지점
    if depth == M:
        new_maps = deepcopy(maps)
        time = bfs(new_maps)
        if time > 0:
            min_v = min(min_v, time)
        else: min_v = time
        return

    for i in range(idx, len_virus):
        if chk[i] == False:
            y, x = virus[i]
            maps[y][x] = 3
            chk[i] = True
            virus_list.append((y, x, 0))
            dfs(i + 1, depth + 1)
            maps[y][x] = 2
            chk[i] = False
            virus_list.pop()

virus_list = []
min_v = 1e9
dfs(0, 0)
if min_v == 1e9: print(-1)
elif min_v == 0: print(0)
else: print(min_v)