백준 17142 연구소 3 (파이썬)

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

17142번: 연구소 3

비활성 바이러스가 있는 칸도 결국은 바이러스가 있는 칸이기 때문에 이를 고려해야한다

그래서 cnt, cnt2, flag, flag2로 조건문을 붙여서 구현

 

1. 초기 입력에서 비활성 바이러스를 배열 안에 저장한다

2. 조합으로 바이러스를 m개 고르는 경우에 대한 리스트를 만든다. 그 후 모든 경우에 대해서 bfs로 검사한다

3. 바이러스의 좌표를 큐에 넣고 각 바이러스에 대한 체크 배열 c를 1로 저장한다

4. 이동한 시간을 세는 cnt 변수가 2개인데 빈칸이 아니라 비활성 바이러스만 지나가는 경우 때문이다

   현재 큐에 있는 바이러스의 좌표를 전부 한칸씩 이동시킨다

5. 이동했으면 flag를 1로 바꾼다. 이동했을 때만 cnt를 증가시켜야 하기 때문이다.

6. 만약 다음칸이 빈칸이면 flag2를 0으로 저장한다

   이동한 모든 칸이 비활성 바이러스가 있는 칸이면 flag2는 1이 된다

7. 바이러스가 이동할 칸이 있는 경우인 flag == 1 일때만 cnt를 증가해야 한다

   만약 flag2가 1일 때는 cnt2만 증가한다.

   - 비활성 바이러스 칸만 이동하다가 끝나는 경우를 고려해서 따로 cnt를 저장하는 변수 cnt2를 만듬

   flag2가 0이고 cnt2가 0이면 빈 칸을 포함하여 이동한 일반적인 케이스로 cnt를 증가한다

   cnt2가 0이 아니면 cnt에 cnt2 + 1을 더하고 cnt2를 초기화한다

   - 비활성 바이러스칸을 따라서 이동하다가 빈칸을 찾게된 경우이다

8. 모든 방문을 끝낸 후 아직 방문하지 못한 0이 있으면 최대정수를 반환하고 아니면 걸린 시간을 출력한다

9. 모든 경우에 대한 검사가 끝난후 ans가 최대정수이면 -1 출력, 아니면 ans 출력

from collections import deque
from itertools import combinations
import sys

input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def bfs():
    cnt, cnt2 = 0, 0
    while q:
        qlen = len(q)
        flag, flag2 = 0, 1
        for idx in range(qlen):
            x, y = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < n and 0 <= ny < n and c[nx][ny] == 0:
                    if a[nx][ny] == 0 or a[nx][ny] == 2:
                        c[nx][ny] = 1
                        q.append([nx, ny])
                        flag = 1
                        if a[nx][ny] == 0:
                            flag2 = 0

        if flag == 1:
            if flag2 == 0:
                if cnt2:
                    cnt += cnt2 + 1
                    cnt2 = 0
                else:
                    cnt += 1
            else:
                cnt2 += 1

    for i in range(n):
        for j in range(n):
            if (a[i][j] == 0 or a[i][j] == 2) and c[i][j] == 0:
                return sys.maxsize
    return cnt


n, m = map(int, input().split())

a, v = [], []
for i in range(n):
    row = list(map(int, input().split()))
    a.append(row)
    for j in range(n):
        if a[i][j] == 2:
            v.append([i, j])

k = list(combinations(v, m))

ans = sys.maxsize
for i in range(len(k)):
    q = deque()
    c = [[0] * n for _ in range(n)]
    for j in range(m):
        x, y = k[i][j][0], k[i][j][1]
        c[x][y] = 1
        q.append([x, y])

    ans = min(ans, bfs())

print(-1) if ans == sys.maxsize else print(ans)