[Baekjoon] 17142번 : 연구소 3 - Python

Gold 4

17142번: 연구소 3

 

문제 풀이

DFS + BFS

처음에 떠올린 방법은 DFS로 활성화 바이러스를 고르는 모든 경우의 수를 탐색하고 입력된 수 만큼 활성화가 되면 그 때 bfs를 호출해서 최단 거리를 구해주는 방법이었다.

딱 봐도 중복된 경우도 탐색하기 때문에 시간이 배로 걸리고 코드도 복잡해지는 방법 ㅎㅎ... 

itertools의 combinations를 이용해 조합을 구해야 한다.

 

비활성화된 바이러스를 만나면 활성화된다는 것이 좀 혼란스러웠는데 그냥 그 친구는 무시하고 해주면 된다,, 

 

 

코드

from collections import deque
from itertools import combinations

def bfs():
    while vir:
        x, y = vir.popleft()
        for i in range(4):
            nx = x + mx[i]
            ny = y + my[i]

            # 범위안에 있고 벽이 아니면서 아직 방문하지 않았으면
            if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == 0 and lab[nx][ny] != 1:
                visited[nx][ny] = 1
                vir.append([nx,ny])
                times[nx][ny] = times[x][y] + 1


minValue = 1e9
maxValue = -1

mx = [-1, 0, 1, 0]
my = [0, -1, 0, 1]

n, m = map(int, input().split())
lab = []
virus = deque()
notWall = 0
answer = 1e9

for i in range(n):
    a = list(map(int, input().split()))
    lab.append(a)
    for j in range(n):
        if a[j] == 2: virus.append([i, j]) # 2이면 바이러스에 추가
        if a[j] != 1: notWall += 1 # 벽이 아닌 칸 수 세기

# 활성화 바이러스 선택 조합
actVirus = list(combinations(virus, m)) # (x, y)

for v in actVirus:
    times = [[-1] * n for _ in range(n)]
    visited = [[0] * n for _ in range(n)]
    vir = deque()

    # 활성화 바이러스가 있는 위치는 방문처리 & 시간 0으로
    for x, y in v:
        vir.append([x, y])
        visited[x][y] = 1
        times[x][y] = 0

    bfs()

    # 방문한 칸의 개수 세기 => 0이 있는지 여부를 확인하는 것보다 빠르낙,,?
    cnt = 0
    for j in visited: cnt += j.count(1)
    # 모두 방문했다면 최대값구하기
    if notWall == cnt:
        maxValue = 0
        for j in range(n):
            for k in range(n):
                # 벽이 아니면서 바이러스가 있는 칸이 아니라면
                if lab[j][k] != 1 and [j, k] not in virus:
                    maxValue = max(maxValue, times[j][k])

        answer = min(answer, maxValue)

print(answer if answer != 1e9 else -1)

 

느낀점

방법이 떠오르는데 머리속에서 정리가 잘 안된다 ㅠㅠㅠ 많이 연습하면 나아질까 ㅠㅠ

참고한 블로그 -> https://pacific-ocean.tistory.com/381