17141: 연구소 2 && 17142: 연구소 3

17141: 연구소 2

• combination을 이용하여 candidate에서 M개의 바이러스를 선택하는 모든 경우를 순회하여 result를 최소시간으로 갱신해줌
• bfs를 통해 모든 경우에 대해 최소시간을 구해줌

import sys
from collections import deque
from itertools import combinations

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def bfs(start):
    queue = deque(start)
    visit = [[-1 for _ in range(N)] for _ in range(N)]
    for i in range(M):
        visit[start[i][0]][start[i][1]] = 0
    
    local_result = 0
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]; ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if visit[nx][ny] == -1 and board[nx][ny] != 1:
                    visit[nx][ny] = visit[x][y] + 1
                    local_result = max(local_result, visit[x][y] + 1)
                    queue.append([nx, ny])

    for i in range(N):
        for j in range(N):
            if visit[i][j] == -1 and board[i][j] != 1:
                return 10e9
    return local_result


N, M = map(int, sys.stdin.readline()[:-1].split())
board = []; candidate = []
for n in range(N):
    tmp = list(map(int, sys.stdin.readline()[:-1].split()))
    board.append(tmp)
    for i in range(N):
        if tmp[i] == 2:
            candidate.append([n, i])

result = 10e9
for start in combinations(candidate, M):
    result = min(bfs(start), result)

if result == 10e9:
    print(-1)
else:
    print(result)

17142: 연구소 3

• "17141: 연구소 2"문제와 유사함
• 한 가지 주의해야할 점은 board[i][j] == 2인 경우도 벽이 아니기 때문에 지나갈 수 있다는 사실
  -> bfs에서 마지막으로 도착한 노드가 board가 2인 경우라면, 이는 최소시간에서 배제해야하기 때문에 local_result를 따로 갱신하지 않아야함

import sys
from collections import deque
from itertools import combinations

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def bfs(start):
    queue = deque(start)
    visit = [[-1 for _ in range(N)] for _ in range(N)]
    for i in range(M):
        visit[start[i][0]][start[i][1]] = 0
    
    local_result = 0
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]; ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if visit[nx][ny] == -1 and board[nx][ny] == 0:
                    visit[nx][ny] = visit[x][y] + 1
                    local_result = max(local_result, visit[x][y] + 1)
                    queue.append([nx, ny])
                elif visit[nx][ny] == -1 and board[nx][ny] == 2: #비활성 바이러스인 경우도 벽이 아니기 때문에 지나갈 수 있음
                    visit[nx][ny] = visit[x][y] + 1
                    queue.append([nx, ny])

    for i in range(N):
        for j in range(N):
            if visit[i][j] == -1 and board[i][j] == 0:
                return 10e9
    return local_result


N, M = map(int, sys.stdin.readline()[:-1].split())
board = []; candidate = []
for n in range(N):
    tmp = list(map(int, sys.stdin.readline()[:-1].split()))
    board.append(tmp)
    for i in range(N):
        if tmp[i] == 2:
            candidate.append([n, i])

result = 10e9
for start in combinations(candidate, M):
    result = min(bfs(start), result)

if result == 10e9:
    print(-1)
else:
    print(result)