연구소 3 [백준 17142번]

문제

 

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

17142번: 연구소 3

 

내 풀이

 

삼성 시험에서는 itertools를 쓸 수 없다고 해서 dfs로 순열을 구현하였다.

dfs로 활성 바이러스가 될 수 있는 애들 M개를 골랐다.

 

M개를 골랐으면, 그 애들을 활성 바이러스로 하여 bfs로 빈칸에 활성 바이러스가 얼마나 퍼지는지 구하였다.

바이러스가 퍼질 때 중요한 것은 비활성 바이러스의 존재이다.

비활성 바이러스는 활성 바이러스와 만나면 활성 바이러스가 되어 빈칸에 바이러스를 퍼뜨릴 수 있지만, 시간 계산할 때에는 비활성 바이러스는 고려하면 안 된다.

즉, 마지막 초인 t초에 비활성 바이러스가 활성 바이러스로 변했다고 해도 답은 t초가 아니다.

중요한 것은 빈칸이다. 빈칸이 모두 활성 함수로 변하기 위해 몇 초가 걸렸는지이다.

 

이것만 잘 기억하면 수월하게 문제를 풀 수 있을 것이다.

나는 바보라서 문제를 이해하는 데에 좀 오래 걸렸다.

 

from collections import deque

N, M = map(int, input().strip().split())
viruses, lab, zero = [], [], 0

for i in range(N):
    arr = list(map(int, input().strip().split()))
    lab.append(arr)
    for j in range(N):
        if arr[j] == 2: viruses.append((i, j))
        elif arr[j] == 0: zero += 1
if not zero:
    print(0)
    exit(0)

def bfs(arr):
    mx = -1e9
    dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
    q = deque()
    visit = [[-1]*N for _ in range(N)]
    for a in arr:
        visit[a[0]][a[1]] = 0
        q.append(a)
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0<=nx<N and 0<=ny<N:
                if visit[nx][ny] == -1:
                    if lab[nx][ny] == 2:
                        visit[nx][ny] = visit[x][y] + 1
                        q.append((nx, ny))
                    elif lab[nx][ny] == 0:
                        visit[nx][ny] = visit[x][y] + 1
                        mx = max(mx, visit[nx][ny])
                        q.append((nx, ny))
    flag = True
    for i in range(N):
        for j in range(N):
            if visit[i][j] == -1 and lab[i][j] == 0: # 빈 칸인데 바이러스가 안 퍼진 경우
                flag = False
                break
        if not flag:
            break
    if flag: return mx
    else: return 1e9

ans = 1e9
check = [False]*len(viruses)
def dfs(cnt, cur):
    global ans
    if cnt == M:
        arr = []
        for k in range(len(viruses)):
            if check[k]:
                arr.append(viruses[k])
        ans = min(ans, bfs(arr))
        return
    for i in range(len(viruses)):
        if not check[i] and cur <= i:
            check[i] = True
            dfs(cnt+1, i)
            check[i] = False

dfs(0, 0)
if ans == 1e9: print(-1)
else: print(ans)

 

총평

문제 이해를 잘 못해서 계속 이상하게 코딩했다.

짜증이 올라왔을 때쯤 이것을 보았고, 내가 왜 잘못 구현했는지 깨닫게 되었다.

 

https://www.acmicpc.net/board/view/98175

글 읽기 - 계속 에러가 뜨시는 분들 참고하셔요