17142번 - 연구소3

문제

 

17142번: 연구소 3 (acmicpc.net)

17142번: 연구소 3

풀이 1

이 문제는 언뜻 보면 지금껏 풀어온 탐색문제와 크게 다를것이 없어보이지만, 함정(?)이 숨겨져있어 주의가 필요하다. 문제를 자세히 읽어보며 어떻게 다른지 잘 파악해야 시간낭비없이 제대로된 설계로 문제를 풀이할 수 있다.

• 문제에서 원하는 상황은 "모든 빈 칸"에 바이러스가 퍼지는 상황이다. 따라서 바이러스 전염 구현이 끝나면 board를 탐색하며 '빈 칸'이 남아있는지 확인할 필요가 있는데, 답이 되는 '최소 시간'역시 0이 될 수 있으므로 '빈 칸'을 어떻게 구분할지에 대한 고민이 필요하다. 따라서 입력으로 주어지는 보드를 그대로 쓰기보다는 풀이 예시처럼 특정 문자로 바꾸는 편이 좋다.
• 비활성화 바이러스에 활성화 바이러스가 닿으면 활성화된다. 그러나 문제에서 원하는 것은 '빈 칸' 이 모두 바이러스로 채워지는데 까지의 시간이므로, BFS로 바이러스 전염을 구현할 때 만약 비활성화 바이러스가 모두 활성화되기 전에 빈 칸이 모두 채워지는 경우 빈 칸이 채워지는 시간까지만을 세어야 한다.
• 결국 바이러스는 이미 지나친 위치나 벽을 제외하고는 모두 지나갈 수 있으므로, 단순히 빈 칸일 때만 전염이 진행되게끔 조건문을 세우면 안된다.

from collections import deque

# 북 서 남 동
dRow = [-1,0,1,0]
dCol = [0,-1,0,1]

N,M = map(int,input().split())
board = []
viruses = []
for row in range(N):
    li = []
    for col,elem in enumerate(map(int, input().split())):
        if elem == 2:
            li.append('*')
            viruses.append((row,col))
        elif elem == 1:
            li.append('-')
        else:
            li.append('o')
    board.append(li)

length = len(viruses)


def spread_viruses(locs):
    visited = [[0]*N for _ in range(N)]
    _board = [[*elem] for elem in board]
    q = deque()
    for _row,_col in locs:
        visited[_row][_col] = 1
        q.append((0,_row,_col))
    while q:
        cnt,_row,_col = q.popleft()
        for i in range(4):
            nRow,nCol = _row+dRow[i],_col+dCol[i]
            if 0 <= nRow < N and 0 <= nCol < N and visited[nRow][nCol] == 0 and _board[nRow][nCol] != '-':
                visited[nRow][nCol] = 1
                if _board[nRow][nCol] == 'o':
                    _board[nRow][nCol] = cnt+1
                q.append((cnt+1,nRow,nCol))
    result = 0
    for _row in range(N):
        for _col in range(N):
            if _board[_row][_col] == 'o':
                return -1
            if type(_board[_row][_col]) == int:
                result = max(result,_board[_row][_col])
    return result


def dfs(cnt, start, visited):
    global answer
    if cnt == M:
        temp = spread_viruses(visited)
        if temp != -1:
            answer = min(answer,temp)
        return
    for i in range(start, length):
        if not viruses[i] in visited:
            dfs(cnt+1, i, visited|{viruses[i]})


answer = int(1e9)
dfs(0,0,set())
if answer == int(1e9):
    print(-1)
else:
    print(answer)

풀이 2

재귀로 각 바이러스 위치의 조합을 만든 후, 해당 바이러스가 퍼지는 것을 distance라는 최단거리를 나타내줄 이차원 리스트와 BFS로 구현하여 바이러스가 전부 퍼졌을 때의 시간을 구하여 answer를 갱신하는 방식으로 접근했다. 하지만 이 방법에는 치명적인 문제가 있는데, 다음과 같은 반례가 생긴다는 것이다

4 1

0 0 0 2

0 0 0 0

1 1 1 0

2 2 1 0

위와 같은 경우 BFS로 바이러스가 퍼지면 다음과 같은 모양이 된다.

3 2 1 -1

4 3 2 1

0 0 0 2

0 0 0 3

활성화 하지 않은 바이러스가 0으로 남는데, distance 리스트에서 빈칸의 개수를 검사하면 오답이 도출되는 것이다.

따라서 좀 더 단순한 방법을 사용하였다. BFS내에서 계속해서 시간을 갱신하고, 보드를 복사해서 visited 처럼 이용하는 것이다. 이렇게 하면 위와같은 상황을 방지할 수 있다.

from collections import deque

dr = [-1,0,1,0]
dc = [0,-1,0,1]

N,M = map(int,input().split())
board = [[0]*N for _ in range(N)]
walls = 0
viruses = []
for i in range(N):
    for j,v in enumerate(map(int,input().split())):
        board[i][j] = v
        if v == 1:
            walls += 1
        elif v == 2:
            viruses.append((i,j))


def get_answer(cnt, start, stack):
    global answer,flag
    if cnt == M:
        # 바이러스 퍼뜨리기
        time = 0
        cpy_board = [[*elem] for elem in board]
        q = deque()
        for r,c in stack:
            q.append((r,c,0))
            cpy_board[r][c] = 1
        while q:
            r,c,t = q.popleft()
            for i in range(4):
                nr,nc = r+dr[i],c+dc[i]
                if 0 <= nr < N and 0 <= nc < N and cpy_board[nr][nc] != 1:
                    if cpy_board[nr][nc] != 2:
                        time = max(time,t+1)
                    cpy_board[nr][nc] = 1
                    q.append((nr,nc,t+1))
        # 검사
        for li in cpy_board:
            if not all(li):
                break
        else:
            answer = min(answer,time)
            flag = True
        return
    # 조합
    for i in range(start,len(viruses)):
        stack.append(viruses[i])
        get_answer(cnt+1,i+1,stack)
        stack.pop()

answer = int(1e9)
flag = False
get_answer(0, 0, [])
if flag:
    print(answer)
else:
    print(-1)