이 세상의 모든 세일즈맨을 위하여 (백준 10971번 : 외판원 순회2)

10971번: 외판원 순회 2 (acmicpc.net)

10971번: 외판원 순회 2

- 대전략

 이 행렬에서 중요한 것은 도시의 시작점인 y=0(x[0])이다. 

결국 이 문제도 N-Queen과 같은 문제가 아닐까. x=i, y=0 을 시작점으로 하고, 0 이 아닌 곳에 가는 경우의 수를 구현해본다. 

그러면 for로 y=0을 돌린다. 그리고 안에서 재귀함수로 실행시켜야 할 것 같다.

만약 (0,0)에서 시작한다면 각각 (0,1) (0,2) (0,3) 선택지가 있다. 그러면 for 문으로 y를 모두 돌려야 할 것이다.

(0,1)을 선택한다면 일단 여행 리스트에 y=1을 추가해야 할 것이다 (두번 방문하지 않기 위해서. 또한, 첫번째 도시로는 다시 와야하기 때문에 시작점은 추가하지 않을 것이다. )

 

y=1이 되었다면 다시 x=1, y=0으로 오고 다시 선택지를 선택한다. (이미 1은 갔으므로 리스트에서 제한한다.)

 

그래서 여행 리스트가 [T, T, T, T] (간 도시의 좌표에 T를 넣었다.) 되었다면 종료하고 경비를 제출한다. 

 

한번 뼈대를 잡아보자.

 

N = int(sys.stdin.readline())
for i in range(N):
    price = [int(x) for x in input().strip().split()]
    route.append(price)

로 입력을 구현한다. 

 

def find(i, fee):
    if visited.count(True) == 0:
        return fee

    for j in range(N): # i -> j 방문
        if route[i][j] != 0 and visited[j] == True:
            visited[j] = False
            print("F확인", visited)
            fee = fee + route[i][j]
            print(i,"에서", j, "방문")
            find(j, fee) 

for i in range(N): # i = 출발 도시
    fee = 0
    print("시작:",i)
    find(i, 0)

그런데 처음 출발한 도시는 마지막에 되돌아와야하므로 시작 도시를 True가 아니라 False로 해줘야할 것 같다. 또한, 마지막 도시에서 원래 도시로 돌아오는 것은 따로 구현해줘야 할 것같다. 

 

 

또한, 맨 처음 출발도시가 바뀔 때, visited를 초기화시켜주고, 처음 도시를 False 시켜 주자.

수정한 코드는 다음과 같다.

import sys

sys.stdin = open("textfile1.txt","rt")
sys.setrecursionlimit(100000000)
# a = int(sys.stdin.readline())
# a,b = map(int,input().split())
# a = [int(x) for x in input().strip().split()]


N = int(sys.stdin.readline())
route = []
fee = 0
visited = []
min_fee = []
for i in range(N):
    price = [int(x) for x in input().strip().split()]
    route.append(price)
    visited.append(True)

#print(visited)

def find(i, fee, first):
    if visited.count(True) == 0:
        fee = fee + route[i][first]
        #print("fee:", fee)
        if len(min_fee) == 0:
            min_fee.append(fee)
        elif min_fee[0] > fee:
            min_fee[0] = fee

        return 

    # i -> j 방문
    for j in range(N):  # 목적지 판별
        #print("i:",i,"j:",j)
        if route[i][j] != 0 and visited[j] == True: 
            #print(i,"에서", j, "방문")
            visited[j] = False
            #print("F확인", visited)

            fee = fee + route[i][j]
            find(j, fee, first) # 다음 도시 방문 

for i in range(N): # i = 출발 도시
    for j in range(N):
        visited[j] = True
    visited[i]=False
    fee = 0
    #print("시작:",i)
    first = i
    find(i, 0, first)

print(min_fee[0])

 

두가지가 마음에 걸리는데 첫째는 마지막 도시에서 첫번째 도시에 갈 수 없는 경우이고 두번째는 과연 모든 경우의 수를 시행하고 있는가 이다.

 

일단 첫번째에 대해서 성공 조건을 다음과 같이 수정하였다. 

    if visited.count(True) == 0 and route[i][first] != 0:
        fee = fee + route[i][first]
        #print("fee:", fee)
        if len(min_fee) == 0:
            min_fee.append(fee)
        elif min_fee[0] > fee:
            min_fee[0] = fee

 

그리고 경우의 수가 제대로 다 돌고 있는지 검증해보았다.

 

딱 봐도 모든 경우의 수가 시행되지 않는 것이 보인다. 

문제는 실패하고 돌아갔을 때, visted에 False가 그대로 남아있어서 나머지 경우의 수도 시행하지 않는 것 같다.

 

그래서 재귀함수를 시행한 다음에 재귀함수 시행 이전에 실시한 False한 Visited를 다시 True로 바꿔주었다.

 

또한, 0 -> 1 -> 2 -> 3 -> 이나 2 -> 3 -> 4 -> 0 -> 1 이나 똑같다. (결국 마지막엔 처음 도시로 오기때문에 원형 경로를 그린다.) 그렇기 때문에 시작 지점을 0 으로 고정한다. (0으로 고정해도 모든 경우의 수를 탐험한다.)

 

코드는 다음과 같다. 

import sys
sys.stdin = open("textfile1.txt","rt")

N = int(sys.stdin.readline())
fee = 0
visited = [True for _ in range(N)]
min_fee = sys.maxsize
route = list(list(map(int,sys.stdin.readline().split())) for _ in range(N))

def find(i, fee, first):
    global min_fee
    if visited.count(True) == 0 and route[i][first] != 0:
        fee = fee + route[i][first]
        min_fee = min(min_fee, fee)
        return 

    for j in range(1, N):

        if route[i][j] != 0 and visited[j] == True: 
            visited[j] = False
            find(j, fee+ route[i][j], first)
            visited[j] = True

visited[0] = False
first = 0
find(0, 0, first)

print(min_fee)