[Python | 파이썬] 백준 17142 연구소3

[Python | 파이썬] 백준 17142 연구소3

 

 

이 문제는 itertools의 combinations을 이용해서 풀 수도 있지만 삼성 sw역량테스트에서는 itertools를 사용할 수 없는 경우가 있어서 저는 dfs를 이용해서 풀었습니다. 시간 제한을 해결하는 게 조금 어려운 문제였습니다.

 

1. 우선 virus는 2 => -2, 벽은 1 => -1로 변경하여 maps배열에서 최대시간을 계산하는 데 헷갈리지 않도록 구현하였습니다. 

2. virus는 virus배열에 x, y를 넣어 추가하고 이후에 dfs에서 이 virus 배열을 이용하여 활성화시킬 바이러스가 m개가 되었을 때 바이러스를 퍼뜨리기 시작합니다.

3. 바이러스가 상하좌우로 도달한 위치에 있는 원소가 벽이 아니라면 이 위치에서 바이러스가 다시 퍼뜨려질 수 있기 때문에 queue에 현재 위치와 시간+1을 추가합니다.

4. 만약 현재 위치가 빈칸이라면 maps[nx][ny]를 현재시간+1로 갱신합니다.

(왜냐하면 이문제는 모든 빈칸이 바이러스가 될때까지의 최소시간이기때문에 바이러스의 위치에도 시간을 넣게되면 이후에 queue에서 모든 원소를 pop해주고 maps배열의 max를 탐색할 때, 최소시간을 구할 수 없게 됩니다. (virus가 있는 위치의 도달 시간이 더 길 수 있기 때문에)

 

이 문제에서 시간제한을 해결하는데 중요했던 것을 몇가지로 정리해보면 아래와 같습니다.

1. cnt가 m이 되고 선택된 m개의 바이러스가 주변으로 퍼뜨려지기 시작할 때 queue에서 pop한 원소의 상하좌우에 있는 원소를 탐색할 때는 반드시 visited 배열로 먼저 탐색하지 않은 위치인지 확인해야한다. ***** 

2. dfs로 탐색할때 매개변수로 현재 활성화시킨 바이러스의 개수 cnt와 현재까지 확인한 바이러스의 인덱스 idx+1를 함께 넣어주고, 매개변수로 주어진 idx부터 활성화를 시키며 dfs를 재귀적으로 진행한다.

 

참고로 제가 구현한 코드는 copy의 deepcopy 모듈을 사용하면 416ms, 직접 일일이 for문으로 대입하면 256ms가 나왔습니다. 저는 visited배열과 maps배열을 cnt가 m이 되었을 때 test_visited배열과 test_maps 배열에 대입하는 방법으로 진행했습니다. 하지만 위의 모든 사항을 고려하여 구현하면 deepcopy모듈을 사용해도 통과되었습니다.

이외에도 min, max 같은 함수 최대한 사용을 자제하고 idx를 사용하면 주석으로 처리된 아래 같은 불필요한 코드를 제거할 수 있었습니다. 또한 active는 dfs로 탐색하여 최상단부터 삭제하는 것이기 때문에 remove를 사용할 필요 없이 pop연산을 사용해도 됩니다. 또 현재배열에서 빈칸이 없을경우는 dfs를 아예 탐색할 필요가 없도록 구현하였습니다.

    for i in range(idx, v):

        #if (virus[i][0], virus[i][1], 0) in active:

        #    continue

        active.append((virus[i][0], virus[i][1], 0))

        dfs(cnt+1, i+1)

        active.pop()

 

 

코드

 

# 17142 연구소3
from collections import deque
import sys
input = sys.stdin.readline

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

n, m = map(int, input().split())
maps = []
visited = [[False] * n for _ in range(n)]
test_visited = [[False] * n for _ in range(n)]
virus = []
active = []
blank = False
for _ in range(n):
    maps.append(list(map(int, input().split())))
test_maps = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if maps[i][j] == 1:
            maps[i][j] = -1
        elif maps[i][j] == 2:
            maps[i][j] = -2
            virus.append((i, j))

v = len(virus)
ans = int(1e9)
flag = False

def dfs(cnt, idx):
    global flag, ans
    local_ans = 0
    if cnt == m:
        for i in range(n):
            for j in range(n):
                test_maps[i][j] = maps[i][j]
                test_visited[i][j] = visited[i][j]
        for x, y, cur_time in active:
            test_visited[x][y] = True
        q = deque(active)
        while q:
            x, y, cur_time = q.popleft()
            for d in range(4):
                nx, ny = x + dx[d], y + dy[d]
                if 0 <= nx < n and 0 <= ny < n and not test_visited[nx][ny]:
                    test_visited[nx][ny] = True
                    if test_maps[nx][ny] == 0:
                        test_maps[nx][ny] = cur_time + 1
                        q.append((nx, ny, test_maps[nx][ny]))
                    elif test_maps[nx][ny] == -2:
                        q.append((nx, ny, cur_time + 1)) 

        for i in range(n):
            for j in range(n):
                if test_maps[i][j] == 0:
                    return
                if local_ans < test_maps[i][j]:
                    local_ans = test_maps[i][j]

        flag = True
        ans = min(ans, local_ans)
        return
    
    for i in range(idx, v):
        active.append((virus[i][0], virus[i][1], 0))
        dfs(cnt+1, i+1)
        active.pop()
        
for i in range(n):
    for j in range(n):
        if maps[i][j] == 0 and not blank:
            blank = True
if not blank:
    print(0)
else:
    dfs(0, 0)
    if not flag:
        print(-1)
    else:
        print(ans)

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