[완전탐색] 백준 외판원 순회 2 10971번 with Python3★★★

 

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

10971번: 외판원 순회 2

문제

이 문제 또한, 시도는 실패했다. 그렇기에 이해하고, 다룰수 있게끔 타인의 풀이를 해체해보자.

 

 

dfs - 깊이 우선 탐색:

def dfs(start, next, value, visited):
    global min_value

    if len(visited) == N:
     #len(visited) == N 인데, 섬의 개수만큼 방문 개수가 됐다면, 모든 섬을 다 한번씩 방문했기에 끝.
        if travel[next][start] != 0: #충분한 깊이/ 순회에서 마지막 섬에서는 도착했는데;
        							# 첫 섬으로 돌아오는 비용이 0이 아니라  양수면.
                                    #아니라면 해당 비용을 추가한 합에 전 합을 비교해
                                    #min_value를 업데이트 하고 탈출.
        
        
            min_value = min(min_value, value + travel[next][start])
            					
                                #min_value는 전역변수다.
                                #이 값을 얻기위해 이렇게 돌고 있다.
         
        return


    for i in range(N):
        if travel[next][i] != 0 and i != start and i not in visited:
        	#1. 다음으로 향할 섬으로 향하는 비용이 0이 아니고 /
            #2. 다시 첫 섬으로 돌아오는 i가 아니고/
            #3. 이미 방문해본 섬/ i 가 아니라면
        	
            visited.append(i)
            
            #우선 해당 섬 i를 visited에 추가해놓고
            
            dfs(start, i, value + travel[next][i], visited)
            
            #1. start지점은 안바뀐다. 항상 섬 1 즉 start == 0
            #2.다음 섬은 i/ 위의 for문에서 조건이 검증된 도착지이다.
            #3. 다음섬으로 향하는 비용을 value에 추가하고, 
            #4.visted라는 스택도 챙기고 재귀 함수 실행
            
            visited.pop()
            
            #충분한 깊이에 도달할경우 탈출을 시작하기에, 그떄마다 그 이전단계에
            #추가했던 visted 스택에서 하날 뺸다. 
            #돌아온다는 것은 말그대로 방문했던 섬에서 그 전단계로 돌아오기에
            #visited가 아니게 되기 때문


if __name__ == "__main__":

    N = int(input())
    travel = [list(map(int, input().split())) for _ in range(N)]
    
    #print(travel) => [[0, 10, 15, 20], [5, 0, 9, 10], [6, 13, 0, 12], [8, 8, 9, 0]]
    

    min_value = sys.maxsize  #min함수로 가장 작은 값을 찾아야하기에 초기값을 최대크기의
    						#정수로 했다.
    
   

    # 각 번호에서 시작 /
    for i in range(N):
        dfs(i, i, 0, [i])

# start = i / 1, 2,3,4 도시에서 출발하는 경우를 모두 탐색
# next = i / 시작 도시에 각 도시로 가는 모든 경우를 위해. 
# 시작 때엔 비용이 당연히 0
# [i]로 시작 도시는 이미 방문했음을 visited에 추가

    print(min_value)

출처:https://jjangsungwon.tistory.com/4

해설

dfs는 tree 처럼 가장 깊이 까지 도달한뒤에 돌아오기 시작하는 탐색 기법이다. 

 

dfs를 구상할 때 첫번쨰

1. 종료조건

2. 분기 개수/ 하노이의 탑 같은 경우 분기가 2개이기에 재귀함수를 두번 넣으면 된다.

3. 구현

 

 

 

완전탐색 기법 사용 + N-queen 식 재귀

import sys 
def move(now, depth):  #이는 깊이 우선 탐색이라는 dfs 기법이다.

    global charge, ans 		#n == depth는 섬의 개수만큼 충분히 가지수를 챙겼을때 라는 조건.
    if depth == n:			  #재귀 특성상 이 재귀가 멈추기위한 조건이 제일 앞에 있다. 
        if path[now][0] > 0:  #path는 아래 정의되어있다. 각 입력 줄이 하나의 리스트로,
        					  #입력받은 순서대로 들어가있는 리스트.
                              #path[now][0]은 1번 섬으로 돌아가는 비용이 0이 아닐경우
                              #즉 1번 섬이 가장 마지막에 오지 않았나 체크함.
            ans = min(ans, charge + path[now][0])
        return 

    visit[now] = 1		#현재/ now 
    
    
    for l in link[now]:      #link[now] = path의 비용중 0이 아닌 것들의 인덱스
    
        if not visit[l]:     #visit[l]의 element가 false 라면.
        						
            charge += path[now][l]
            
            move(l, depth+1)   
            
            charge -= path[now][l] 
            
    visit[now] = 0 
    
    

n = int(sys.stdin.readline()) 

path = [list(map(int, sys.stdin.readline().split())) for _ in range(n)] 

visit = [0] * n 		#0혹은 false 값이 차있는 리스트 생성. 검증용/ 같은 행이 반복되지 않게끔.	

link = {}                #link는 딕셔너리형
charge, ans = 0, 10**7   #ans는 min함수를 이용하기위해 각 행렬의 최대값으로 미리 주어졋다.

for i in range(n): 		#딕셔너리 link에
    link[i] = []        #각 index i가 해당하는 곳에
    for j in range(n): 
        if path[i][j] > 0:    
            link[i].append(j)  #path에 저장되어있는 link
            
#print(link) = {0: [1, 2, 3], 1: [0, 2, 3], 2: [0, 1, 3], 3: [0, 1, 2]}
#path[i]의 i가 key, path[i][j] 중 0이 아닌 것들의 index 값이 저장됬다.
            
move(0, 1) 
print(ans)

출처:https://suri78.tistory.com/152