[BOJ] 17142번 - 연구소 3 (삼성 SW 기출)

단순 BFS 문제라 로직은 쉽게 짰는데 문제를 꼼꼼히 읽지 않아서 계속 83%에서 틀렸다..

문제를 꼼꼼히 읽겠다는 다짐은 매번하는데 잘 바뀌어지지 않는다.

앞으로는 확실히 이해한 뒤 키보드에 손을 얹는걸로..

 

www.acmicpc.net/problem/17142

17142번: 연구소 3

 

바이러스 퍼지는 연구소 문제는 몇 번 나와서 몇번 풀어본 사람이라면 비슷하게 풀었을 것이다.

바이러스 조건을 자세히 봐야한다.

만약 바이러스가 총 6개 중에 2개만 이용했을 때 최솟값을 고르라 하면, 6C2만큼 bfs를 통해 탐색해야 할것이다.

 

단, 주의할 경우 한가지

6개 바이러스 중 2개가 선택 될 때 나머지 4개는 비활성 바이러스며, 꼭 활성바이러스가 닿게되면 그제서야 활성바이러스가 된다.

문제에서는 벽을 제외한 모든 곳이 바이러스가 퍼지게 된다고 했는데, 만약 비활성 바이러스가 활성바이러스로 바뀌는 경우가 마지막

시간이 될 수도 있어 원하는 답을 못 구할 수 있다. 따라서 최종 시간이 비활성 바이러스 였던 것도 아니어야 한다.

3 1

0 0 2

2 0 0

0 2 2

 

이 경우 3이 나올 수 있으며, 이 예외 케이스를 잘 고려해줘야 한다.

 

1. 바이러스가 될 수 있는 좌표의 조합을 구한다.

2. 조합을 순회하면서 bfs를 돌린다.

3. bfs돌린 뒤 아직 바이러스에 감염되지 않은 지역이 있는지 체크한다. (나는 체크와 동시에 max값도 구했다.)

 

from sys import stdin
from copy import deepcopy

std = stdin.readline
lab = []
N, T = map(int, std().split())
for i in range(N):
    lab.append(list(map(int, std().split())))

virus = []
for i in range(N):
    for j in range(N):
        if lab[i][j] == 1:
            lab[i][j] = -1
        elif lab[i][j] == 2:
            lab[i][j] = -3
            virus.append((i, j))
virus_combi, c = [], []
check = [0 for i in range(len(virus))]


def combi(n, start):
    if len(c) == n:
        virus_combi.append(list(c))
        return

    for i in range(start, len(virus)):
        if check[i] == 0:
            check[i] = 1
            c.append(virus[i])
            combi(n, i+1)
            c.pop()
            check[i] = 0


combi(T, 0)
a, q = [], []
nr, nc = [0, 1, 0, -1], [1, 0, -1, 0]


def bfs():
    while q:
        r, c, d = q.pop(0)
        for i in range(4):
            dr, dc = r+nr[i], c+nc[i]
            if 0 <= dr < N and 0 <= dc < N and (a[dr][dc] == 0 or a[dr][dc] == -3):
                a[dr][dc] = d+1
                q.append((dr, dc, d+1))


answer = 2501


for vi in virus_combi:
    a, ans = deepcopy(lab), 0
    for v in vi:
        r, c = v
        a[r][c] = -2  # 활성상태는 -2로하자
        q.append((r, c, 0))

    bfs()
    for i in range(N):
        flag = False
        for j in range(N):
            if a[i][j] == 0:
                ans = -1
                flag = True
                break
            elif a[i][j] > 0 and not lab[i][j] == -3:
                if a[i][j] > ans:
                    ans = a[i][j]
        if flag:
            break
    if ans >= 0 and answer > ans:
        answer = ans


print("-1" if answer == 2501 else answer)