[백준] [DFS] [백트래킹] 10971. 외판원 순회2

10971. 외판원 순회2

10971번: 외판원 순회 2

 

파이썬

• 다른 사람 풀이
  • 나도 백트래킹 까지는 접근 했음
  • visited는 밖에서 값 변경해주고 파라미터에 넣지 않아도 해당 값을 가지고 dfs가 실행됨
  • 처음 시작하는 도시만 바깥 for문에서 돌려주고
  • 그 이후는 dfs코드 안에서 다시 for문을 돌면서 다른 도시 탐색
    • 그때도 똑같이 방문처리 했다가, 안한것처럼 돌려놔야함
  • 📍오류 생긴 이유: cost[s][e] 의 값이 0이 아닌지 확인을 꼭 해줘야함 -> 왜?
  • value> answer 일땐 확인할 필요없으니까 return하는 조건
    • -> 시간을 엄청 많이 줄인다!! 꼭 넣어주기

# n개의 도시를 거쳐 다시 원래 도시로
#맨처음 도시만 중복
# 최소 비용
def dfs(start,now,value,cnt):
    global answer
    if cnt==n:
        if cost[now][start]:
            value +=cost[now][start]
            answer=min(answer,value)
        return
  
    if value>answer: # 이 조건 하나로 시간엄청 줄임
        return
  
    for j in range(n):
        if now==j: continue
        if visited[j]==False and cost[now][j]:
            visited[j]=True
            dfs(start, j,value+cost[now][j], cnt+1)
            #방문한 것 보내고 나서 다음 처리를 위해 다시 방문 안한 것처럼 돌려놔야함
            visited[j]=False 


n=int(input())
cost=[]
for i in range(n):
    cost.append(list(map(int,input().split())))

visited=[False for _ in range(n)]
answer=int(1e9)

for i in range(n):
    visited[i]= True # visited 파라미터에 담지 않아도 이 상태로 받아들임
    dfs(i,i,0,1)
    visited[i]=False

print(answer)

 

자바

https://yygs321.tistory.com/348