[백준] 2098 외판원 순회, python

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

2098번: 외판원 순회

비트마스크와 동적 계획법을 사용해서 최소비용을 구하는 문제이다.

2차원 배열을 사용해서 푸는데, 상태는 지금까지 선택한 것들을 넣으면 되지만 row 값을 고르는게 오래걸렸다. 이전 값을 넣어야할지 현재 값을 넣어야할지 막막해서 결국 찾아보았고 현재 방문한 도시 번호를 넣는 걸로 하게 되었다. (이건 다른 문제를 더 많이 풀어보면서 감을 익혀야할거같다.)

알고리즘자체는 어제 푼 문제와 비슷하지만 중간중간에 처리해야하는 부분이 조금 다르다. 같은 도시를 방문한 적이 있는지, 갈수 있는 길인지 확인해야하고, 모든 도시를 순회했을 때 마지막 도시에서 처음 도시를 다시 돌아올수 있는지도 확인해야한다.

import sys; input = sys.stdin.readline
INF = 1234567890
def backtrack(cur, limit, state, memo, arr):
    if state == (1 << limit) - 1:
        if arr[cur][0]:
            return arr[cur][0]
        return INF

    if memo[cur][state] != -1: # check visit
        return memo[cur][state]

    memo[cur][state] = INF
    for i in range(limit):
        if cur == i:            continue
        if state & (1 << i):    continue
        if not arr[cur][i]:     continue

        next_state = state | (1 << i)
        next_val = backtrack(i, limit, next_state, memo, arr) + arr[cur][i]

        if memo[cur][state] > next_val:
            memo[cur][state] = next_val
    return memo[cur][state]

def main():
    N = int(input())
    _map = [list(map(int, input().split())) for _ in range(N)]
    memo = [[-1 for _ in range(1 << N)] for _ in range(N)]
    answer = backtrack(0, N, 1, memo, _map)

    print(answer)

if __name__ == '__main__':
    main()

오늘은 C++ 패스...

아마 손에 익을때까지 동적 계획법 + 비트마스크 + dfs(bfs) 문제를 풀 것 같다.