DFS/BFS를 활용한 TSP 문제의 해결

**DFS/BFS를 푸는 방법

무조건, TREE부터 그리고 그 TREE의 특징을 이해하자. 

EX) 한번 간 경로만 구하면 된다.

EX) 밑의 TSP는 DEPTH가 N이고(N-1)  그때 다음에 갈 곳이 START일때만 종료된다. 

 

즉, BACKTRACKING의 조건 OR 가지치기의 조건을 잘 생각하자

 

 

백준 10971

 

TSP 문제를 도전하였으나, 실패 하였다. 

 

일단 코드를 작성하고 , 그 흐름을 작성하겠다.

 

import sys

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

forloop = 0

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

visited = [0] * (N)

m = float('inf')

def DFS(depth,start,cost) :

    global m

    #무한대값을 받아오자

    if depth == (N-1) and costlist[start][0] != 0 :

        #다시 돌고있는 반복인데, (처음이 0 )

        m = min(m,cost+costlist[start][0])

        return

   

    for i in range(N) :

        if visited[i] == 0 and costlist[start][i] != 0 :

            visited[i] = 1

            DFS(depth+1,i,cost+costlist[start][i])

            visited[i] = 0

visited[0] = 1

#중간에 돌아갈 수 없는 .

DFS(0,0,0)

print(m)

   

 

1. 문제에서, I->J와 J->I의 경로가 다를 수 있음을 표현했으므로, 인접 행렬로만 풀이가 가능하다. 

 

2. 그렇게 형성된 인접 행렬이면서 한 경로로 끝까지 가야하는 경우에는, 굳이 INDEX와 N을 맞출 필요가 없다. 

(TIP : 인접 행렬의 경우에는 경험상 FOR I IN RANGE(LEN(ARRAY)OR N ))을 사용하는것이 풀이가 용이하다. )

 

3. 경로를 저장할 필요는 없으므로, VISITED 행렬을 활용하는 것이 유리하다. 

 

이문제에서 반드시 주의해야할 점들이 있었다.

 

1. TSP는 , 어디에서 시작점을 잡든 그 최소 경로가 동일하다. 

 

2. DEPTH가 0 부터 시작했다고 했을때, 모든 경로를 지나 0에 도착하려면 최소 N이상의 깊이를 지나야한다.

 

3. 뿐만 아니라 , 경로를 다 지나는 최솟 값은 그 깊이가 오로지 N일 때만 가능하다. 

그러므로, DEPTH == N-1(N이4일시 0부터 3까지) 일떄, 0으로 갈 수 있는 경우에만 최솟값이 나온다

0 -> 1-> 2->3 (이제야 조건만족했다! 이제 다른곳 겹치지말고 바로 0으로 가야한다! 다른 곳을 또 가면 중복이다) -> 0

과같이 말이다. 

 

4. 예전에도 고민했던 개념인, 재귀 호출 후 VISITED를 취소하면 된다.  

 

5. 이렇게 한번의 경로를 저장하려면, 원하는 값을 매개변수로 전달하면 RETURN이 된 이후로 그 값들이 모두 처음 호출로 올라가게 됨을 기억하자! 

(이번엔 DEPTH였지만, ARRAY가 될수도 있고 , COST가 될수도 있고.)

 

풀 수 있었을거 같은데, TSP의 경우가 DEPTH (0부터시작했을때) == N-1일때, 다음 경로가 0인 경우만 

가능하다는 것을 생각 하지 못했다.