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

문제:www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

 

 

import sys
N = int(sys.stdin.readline().rstrip())
li=[]
for _ in range(N):
    li.append(list(map(int,sys.stdin.readline().rstrip().split())))
travel=[False]*N
final=0
ret=10000000000
def func(y,x,final,ans,cnt):
    global ret
    ans+=li[y][x]
    for i in range(N):
        if not travel[i] and li[x][i]!=0:
            travel[i]=True
            func(x,i,final,ans,cnt+1)
            travel[i]=False
    if cnt==N:
        if li[x][final]!=0:
            ans+=li[x][final]
            ret=min(ret,ans)
            return
        else:
            return



for i in range(N):
    for j in range(N):
        if i!=j and li[i][j]!=0:
            travel[i]=True
            travel[j]=True
            final=i
            func(i,j,final,0,2)
            travel[i]=False
            travel[j]=False
print(ret)

위의 코드는 내 풀이다. 풀이방법은 모든 점을 방문하는 것인데 이 때 cnt가 탈출 조건이다. cnt==N이고 마지막 도착점이 0이 아니라면 결과값을 비교하고 그렇지 않다면 그냥 return하는 식이다. 방문 여부는 travel로 bool값을 통해 확인한다. (위의코드는 pypy3로는 통과했지만 python3로는 시간초과가 나왔다.)

 

 

 

 

 

N=int(input())
W=[list(map(int,input().split()))for i in range(N)]
V=[0]*N
M=1e10
def back_track(n,c):
    global N,W,V,M
    if c<M:
        if all(V) and n==0:
            M=min(M,c)
        for i in range(N):
            if W[n][i]>0 and not V[i]:
                V[i]+=1
                back_track(i,c+W[n][i])
                V[i]-=1
back_track(0,0)
print(M)

위의 코드는 맞은사람 python3에서 상위에 있는 코드이다. 

함수 back_track(n,c)에서 n은 다음 위치를,c는 비용에 관한 것이다. 처음 if문은 이제 쓸데없는 연산을 멈추기 위한 수단이다. 만약 처음에 c가 39가 나와서 M이 39로 초기화 되었는데 다음 연산에서 42가 나오면 다음 것은 볼 것도 없으므로 넘기는 것이다. 다음 if문은 all(V)는 모든 위치를 방문 했느냐를 묻는 것이고 최종 목적지가 0이므로 n==0 인 경우에만 M값을 갱신 시켜준다.

 

all(x)는 반복 가능한(iterable) 자료형 x를 입력 인수로 받으며 이 x의 요소가 모두 참이면 True, 거짓이 하나라도 있으면 False를 돌려준다.

 

for문에는 모든 점들을 방문하는데 0값이 아니고 아직 방문 하지 않은 점들만 방문을 한다.

 

위의 코드를 보고나서 내 코드를 수정한 결과 python3로 시간초과가 안나고 통과하였다.

 

 

 

import sys
N = int(sys.stdin.readline().rstrip())
li=[]
for _ in range(N):
    li.append(list(map(int,sys.stdin.readline().rstrip().split())))
travel=[False]*N
final=0
ret=10000000000
def func(y,x,final,ans,cnt):
    global ret
    if ans<ret:
        ans+=li[y][x]
        for i in range(N):
            if not travel[i] and li[x][i]!=0:
                travel[i]=True
                func(x,i,final,ans,cnt+1)
                travel[i]=False
        if cnt==N:
            if li[x][final]!=0:
                ans+=li[x][final]
                ret=min(ret,ans)
                return
            else:
                return
    else:
        return



for i in range(N):
    for j in range(N):
        if i!=j and li[i][j]!=0:
            travel[i]=True
            travel[j]=True
            final=i
            func(i,j,final,0,2)
            travel[i]=False
            travel[j]=False
print(ret)

기존 코드에서 if ans<ret: else: return 이 두 줄만 추가하였다. 미리 계산하지 않을 것을 넘기니 시간초과 문제를 해결하였다.