[백준, 파이썬, 10971번] 외판원 순회 2

 

풀이

 

• 처음엔 문제를 이해하지 못하고
• 각 지역이 어디지 싶었는데 문제중
• "1번부터 N번까지 번호가 매겨져 있는 도시들이 있고" 라는 문장을 보고 알게 되었다...
• 무튼 해당 문제는 정해져 있는 도시의 수가 아닌 N개의 도시의 수이기에
• 반복문으로 계속 탐색하는 건 무리가 있다고 판단해
• 재귀를 사용해 백트래킹 하여 문제를 해결하고자 했으며
• 그래서 열에 관련한 visit2와 행에 관련한 visit에 방문 체크를 통해 문제 해결
• 여기서 조건문인 val > result: return 의 가지치기를 활용해 시간 단축을 했다.

 

import sys

input = sys.stdin.readline

def find(cnt,val,before):

    global result

    if cnt == n and result > val:

        result = val

        return

    if val > result: return

    for i in range(n):

        if not visit[i] and not visit2[before] and mtx[before][i]:

            visit[i],visit2[before],val = 1,1,val+mtx[before][i]

            find(cnt+1,val,i)

            visit[i],visit2[before],val = 0,0,val-mtx[before][i]

    return

n = int(input())

mtx = [list(map(int,input().rstrip('\n').split())) for _ in range(n)]

result = sys.maxsize

visit,visit2 = [0]*n,[0]*n

find(0,0,0)

print(result)