백준 17142 연구소 3 (Python)

문제 

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

 

나의 접근법

먼저 바이러스 중에서 M개를 선택하는 조합의 경우를 모두 구합니다. 그리고 난 뒤 그래프의 모든 곳을 방문해야 하는데 이를 위해 DFS와 BFS중 무엇을 사용할지 고민 했습니다.

구현을 바로 하기 전에 먼저 DFS로 머리 속에서 시뮬레이션을 돌려봤습니다.

 

1. DFS로 할 경우 첫번째로 선택한 바이러스의 위치가 모든 곳을 탐색하고 이동할 때 마다 시간을 적습니다.

2. 그 다음 바이러스가 탐색할 때 첫번째 바이러스가 저장한 장소 중 자신이 탐색하는 시간보다 큰 경우에만 탐색을 하며 시간을 업데이트 합니다.

위 방식으로 하게 되면 불필요한 계산이 생기고 방문했던 곳을 또 방문하게 된다면 visited 판단에서 에러가 발생하는 위험이 있다고 판단하여 DFS대신 BFS로 풀게되었습니다.

 

1. BFS로 하게 된다면 동시에 M 마리를 커버해야하는데 여기서 동시성과 동기화 문제가 생각났습니다. 제가 선택한 바이러스 순서가 달라지는 경우 결과가 변하면 조합으로 풀 수 없기 때문입니다. 그런데 위 문제는 다행히도 바이러스의 순서에서는 큰 문제가 발견되지 않았습니다.  이유는 하나의 빈칸에서 두개 이상의 바이러스와 떨어진 거리가 같은 경우 어떤 것을 선택해도 BFS로 하는 경우 겹치거나 문제가 되지 않았습니다. 

2. 바이러스를 2에서 -1로 변경했습니다. 이유는 바이러스가 벽인지 빈칸인지 다른 바이러스가 방문한 곳인지 판단하기 위해서는 2는 위험하기 때문이었습니다.

 

3. BFS 안에서는 임시 그래프에선 바이러스의 위치를 0으로 바꿔 시간을 0초로 표현했습니다.

4. M = 3 이라면 3마리를 큐에 한번에 넣어 BFS를 돌리고 -1을 만나면 활성화가 된 것을 q로 넣은 것으로 만들었습니다

5. 마지막 빈칸을 확인하기 위해 다시 바이러스를 -1로 바꾸고 0의 개수를 세어주고 Empty 변수로 빈 곳의 유무를 판단했습니다.

 

제출 코드 (정답)

from itertools import combinations
from collections import deque

def BFS(selectVirus, tempG):
    global ans
    count = 0
    visited = [[0] * N for i in range(N)]
    q = deque([])
    activeVirus = deque([])
    for i in range(len(selectVirus)):
         virus = selectVirus[i]
         q.append([virus[0], virus[1]])
         activeVirus.append([virus[0], virus[1]])
         visited[virus[0]][virus[1]] = 1
         tempG[virus[0]][virus[1]] = 0

    while q:
        x, y = q.popleft()
        visited[x][y] = 1
        for dx, dy in (1, 0), (-1, 0), (0, 1), (0, -1):
            nx, ny = x+dx, y+dy
            if nx < 0 or nx >= N or ny < 0 or ny >= N: continue
            if visited[nx][ny]: continue
            # 이미 다른 바이러스가 방문
            if (tempG[nx][ny] <= tempG[x][y]+1) and visited[nx][ny]: continue
            if (nx, ny) in activeVirus: continue
            # 비활성 바이러스가 있을 때 => 활성바이러스로
            if tempG[nx][ny] == -1 and not visited[nx][ny]:
                visited[nx][ny] = 1
                q.append([nx, ny])
                tempG[nx][ny] = tempG[x][y] + 1
                continue

            if (-1 < tempG[nx][ny] < 1) and not visited[nx][ny]: #빈칸인 경우만
                tempG[nx][ny] = tempG[x][y]+1
                q.append([nx, ny])
                count = max(count, tempG[nx][ny])
                visited[nx][ny] = 1

    for i in range(len(selectVirus)):
        virus = selectVirus[i]
        tempG[virus[0]][virus[1]] = -1

    for i in tempG:
        if 0 in i:
            return -1

    return count

N, M = map(int, input().split())
virusList = []
graph = []
entireCheck = int(10e9)
for i in range(N):
    graph.append(list(map(int, input().split())))
    for j in range(N):
        if graph[i][j] == 2:
            virusList.append([i, j])
            graph[i][j] = -1

def combi(i):
    if len(tempcombi) == M :
        # 대입이 아닌 리스트 슬라이스로 값만 복사하기
        vCombi.append(tempcombi[:])
        return

    for j in range(i, len(virusList)):
        if virusList[j] not in tempcombi:
            tempcombi.append(virusList[j])
            combi(j+1)
            tempcombi.pop()

vCombi = []
tempcombi = []
combi(0)
v = list(combinations(virusList, M))
result = []
Empty = True  # 빈칸이 남아있는 경우

for selectVirus in vCombi:
    tempG = [i[:] for i in graph]
    ans = BFS(selectVirus, tempG)
    if ans >= 0:
        Empty = False
        entireCheck = min(ans, entireCheck)
    result.append(ans)

if not Empty:
    print(entireCheck)
else:
    print(-1)

 

다른 정답 코드 (훨씬 깔끔)

from itertools import combinations
from collections import deque
import sys
input = sys.stdin.readline
def bfs():
    while a:
        x, y = a.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and visit[nx][ny] == 0 and s[nx][ny] != 1:
                visit[nx][ny] = 1
                a.append([nx, ny])
                cs[nx][ny] = cs[x][y] + 1
dx = [1, -1, 0, 0] 
dy = [0, 0, -1, 1]
n, m = map(int, input().split())
s = []
q = []
b = 0
inf = 100000000
result = inf
for i in range(n):
    a = list(map(int, input().split()))
    s.append(a)
    for j in range(n):
        if a[j] == 2: q.append([i, j])
        if a[j] != 1: b += 1
cq = list(combinations(q, m))
for i in cq:
    cs = [[-1] * n for i in range(n)]
    visit = [[0] * n for i in range(n)]
    a = deque()
    for x, y in i:
        visit[x][y] = 1
        cs[x][y] = 0
        a.append([x, y])
    bfs()
    cnt = 0
    for j in visit: cnt += j.count(1)
    if b == cnt:
        max_n = 0
        for j in range(n):
            for k in range(n):
                if s[j][k] != 1 and [j, k] not in q:
                    max_n = max(max_n, cs[j][k])
        result = min(result, max_n)
print(result if result != inf else -1)

후기

깔끔하지는 않지만 검색 없이 반례만으로 정답을 맞은 최초의 문제라서 너무 기뻤습니다. 처음부터 끝까지 제 생각을 따라 구현한 것이 정말 오랜만이라 %가 올라갈 때 마다 마음졸였는데 정답을 맞아서 많이 놀랐고 그리고 처음으로 그림이나 순서를 머리속으로만 생각하고 풀었는데 맞아서 신기했습니다.

그래도 제 코드는 깔끔한 정답은 아니기에 정답을 검색해봤는데 역시 기대했던 대로 저보다 훨씬 깔끔했습니다.

그리고 오늘 문제가 생각보다 난이도가 높아서 더더욱 놀랐습니다. 저는 사실 정답률을 보고 풀지 않습니다. 정답률이 30% 이하이면 지레 겁을 먹고 정답률이 낮으니 틀려도 괜찮다고 위안을 삼아 제 실력 발휘를 하지 못할수도 있기 때문입니다.

이번 문제도 난이도는 최대한 안보고 풀었는데 이것 또한 문제를 푸는데 큰 도움이 되었던 것 같습니다.