[BOJ] 10971. 외판원 순회 2

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

10971번: 외판원 순회 2

 

 

1. 해결항법

순회라는 조건이 붙었다.

예를 들어 문제의 N이 4라면 시작점에서 부터 순회를 해야하고 4이기 때문에 정사각형의 모형으로 순회를 할 것이다.
이 점을 유의하고 완전탐색 백트래킹 방법으로 하면 된다.

본인도 문제 이해가 어려웠고, 어떻게 순회하면서 재귀를 돌 것인가에 대해서 고민을 엄청 했다.
이에 관련해서는 코드에서 dfs() for문을 확인해보면 된다.

 

 

2. 정답코드

import sys
input = sys.stdin.readline


N = int(input())
maps = [list(map(int, input().split())) for _ in range(N)]


# dfs
def dfs(start, now, num, count):
    global answer
    if count == N:
        if maps[now][start] != 0:
            num += maps[now][start]
            answer = min(answer, num)
        return

    for j in range(N):
        if chk[j] == False and maps[now][j]:
            chk[j] = True
            dfs(start, j, num + maps[now][j], count + 1)
            chk[j] = False


# main
chk = [False] * (N)
answer = sys.maxsize

for i in range(N):
    if chk[i] == False:
        chk[i] = True
        dfs(i, i, 0, 1)
        chk[i] = False

print(answer)