17142 - 연구소 3

 

---

 

문제

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

17142번: 연구소 3

 

풀이

 

조합과 bfs로 풀이할 수 있는 문제다.

 

1. 우선 바이러스 있는 위치의 조합을 모두 구한다.

 

2. 조합을 돌면서 bfs를 수행한다. 

 

3. 최솟값을 구한다.

 

대략적인 풀이는 이러한데 중요한 부분이 있다.

목표가 모든 칸의 바이러스 점령이므로, 비활성 바이러스를 꼭 활성화 해줄 필요는 없다.

'비활성 바이러스' 그 자체도 바이러스기 때문에 정확한 목표는 주어진 입력값에서 0 부분이 모두 바이러스화 되어있으면 된다.

 

따라서 초기 배열에서 0의 개수를 확인한다음에, bfs를 돌때 0의 개수 만큼 탐색이 이루어지면 탈출하고, 최솟값을 갱신해주면 된다.

 

코드

import itertools
import sys
from sys import stdin
from collections import deque

def bfs(positions):
    global dx, dy, lab, answer, n, numOfZero
    distance = [[0] * n for _ in range(n)]
    visited = [[False] * n for _ in range(n)]
    q = deque()
    m_value = 0
    # multiple start
    for p in positions:
        q.append((p[0], p[1]))
        visited[p[0]][p[1]] = True

    flag = False
    zeroCnt = 0
    while q:
        x, y = q.popleft()
        for i in range(4):
            if numOfZero == zeroCnt:
                break

            nx = x+dx[i]
            ny = y+dy[i]

            # 범위에 들어가고, 벽이 아니고, 방문하지 않았다면
            if 0 <= nx < n and 0 <= ny < n and lab[nx][ny] != 1:
                if distance[nx][ny] == 0 and not visited[nx][ny]:

                    if lab[nx][ny] != 2:
                        zeroCnt +=1
                    visited[nx][ny] = True
                    distance[nx][ny] = distance[x][y] +1
                    m_value = max(m_value, distance[nx][ny])
                    q.append((nx, ny))

        # 모든 칸들이 점령 되었다면
        if numOfZero == zeroCnt:
            flag = True
            break

    if not flag:
        return

    answer = min(answer, m_value)


n, m = map(int, stdin.readline().rstrip().split())
lab = [ list(map(int, stdin.readline().rstrip().split())) for _ in range(n) ]
check = [[False] * n for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
answer = sys.maxsize
numOfZero = 0
virusPositions = []
for i in range(n):
    for j in range(n):
        if lab[i][j] == 0:
            numOfZero +=1
        if lab[i][j] == 2:
            virusPositions.append([i, j])

combi = itertools.combinations(virusPositions, m)
for c in combi:
    bfs(c)

print(answer) if answer != sys.maxsize else print(-1)

 

후기

 

처음에 계속 시간초과가 나서 , 더이상 최적화 할 수 없는 코드까지 줄였다.

그래도 계속 나길래 원인이 뭔가 했더니..

 

조합이 아니라 순열을  구해서 bfs를 돌리고 있었다. 바보 멍청이다.. 

항상 내 코드를 의심해보자