[백준][구현] 연구소 3

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

17142번: 연구소 3

 

내가 작성한 코드

from collections import deque, defaultdict

dir = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def read_data():
    N, M = map(int, input().rstrip().split())
    z = 0
    virus = []
    board = []
    for r in range(N):
        board.append(list(map(int, input().rstrip().split())))
        for c in range(N):
            if board[r][c] == 0:
                z += 1
            elif board[r][c] == 2:
                virus.append((r, c))
    return N, M, board, z, virus

def in_range(r, c, N):
    return 0 <= r < N and 0 <= c < N

def get_time(board, crnt_virus, z):
    visited = defaultdict(bool)
    q = deque()
    for v in crnt_virus:
        visited[v] = True
        q.append((*v, 0))

    while q:
        r, c, t = q.popleft()

        for d_r, d_c in dir:
            nw_r, nw_c =r+d_r, c+d_c
            if in_range(nw_r, nw_c, N) and board[nw_r][nw_c] != 1 and not visited[(nw_r, nw_c)]:
                visited[(nw_r, nw_c)] = True
                if board[nw_r][nw_c] == 0:
                    z -= 1
                if z == 0:
                    return t+1
                q.append((nw_r, nw_c, t+1))
    return float('inf')

def get_all_case(N, M, board, z, virus, crnt, i):
    if M == 0:
        return get_time(board, crnt, z)
    if len(virus) == i:
        return float('inf')

    return min(get_all_case(N, M-1, board, z, virus, crnt + [virus[i]], i+1),
               get_all_case(N, M, board, z, virus, crnt, i+1))

def get_answer(N, M, board, z, virus):
    if z == 0:
        return 0
    answer = get_all_case(N, M, board, z, virus, [], 0)
    if answer == float('inf'):
        return -1
    return answer

def test():
    N, M = 50, 10
    z = 0
    virus = []
    board = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(10):
        board[i][i] = 2
    for r in range(N):
        for c in range(N):
            if board[r][c] == 0:
                z += 1
            elif board[r][c] == 2:
                virus.append((r, c))
    return N, M, board, z, virus


N, M, board, z, virus = read_data()
# N, M, board, z, virus = test()
print(get_answer(N, M, board, z, virus))

• itertools 없이 Combination 구현
  
  • recursion
    - min(현재 virus 선택, 현재 virus 선택 x)
  • 선택해야하는 개수 == M

 

다른 사람이 작성한 코드

None

• 강한 구현문제로 다른 코드를 참고하지않음

 

기억해야할 것