백준 10971, 외판원 순회 2

백준 10971, 외판원 순회 2

2023.05.21 - [알고리즘] - DFS 순열, 조합

 

도시 1,2,3,4 방문한다고 하면

시작도시를 1이라 정하자,

그러면 2,3,4의 순열 조합으로 나열한 뒤 시작도시, 끝도시를 1로 설정하면 된다.

 

---

이런 식으로 코드를 짜기 어렵게 느껴졌다.

참고용 코드를 보며, 왜 이렇게 하는지 따라가 모든 도시를 방문하는 순열조합을 출력해봤다.

그러니 코드가 이해된다!!!

 

나는 모든 경우를 다 탐색하는 부르트포스 방식으로 문제를 풀어봤다.

 

 

📄 test.py

# 출발지 도착지 제외하고 순열

N = 4

visited = [False]*N
perm = []

def dfs(n, start):
    if n == 0:
        perm.append(start+1)
        print(*perm)
        perm.pop()
        return
    for i in range(N):
        if visited[i] == False:
            visited[i] = True
            perm.append(i+1)
            dfs(n-1, start)
            visited[i] = False
            perm.pop()

for i in range(N):
    visited[i] = True
    perm.append(i+1)
    dfs(N-1, i)
    visited[i] = False
    perm.pop()

 

📄 출력

1 3 2 4 1
1 3 4 2 1
1 4 2 3 1
1 4 3 2 1
2 1 3 4 2
2 1 4 3 2
2 3 1 4 2
2 3 4 1 2
2 4 1 3 2
2 4 3 1 2
3 1 2 4 3
3 1 4 2 3
3 2 1 4 3
3 2 4 1 3
4 2 1 3 4
4 2 3 1 4
4 3 1 2 4
4 3 2 1 4

---

 

📄 최종 제출 코드1

 

현재(cur)에서 다음 도시(next)로 가는 비용은 W[cur][next]만큼 든다.

# 시작 도시(1~4) 저장, 다시 돌아와야 하니깐
# 순열

N = 4
W = [[0,10,15,20],[5,0,9,10],[6,13,0,12],[8,8,9,0]]

visited = [False]*N
costs = []

def dfs(n, start, cur, cost):
    if n == 0:
        cost += W[cur][start]
        costs.append(cost)
        return
    for i in range(N):
        if visited[i] == False:
            visited[i] = True
            # i 자체가 방문표시하고 다음 도시가 되는 것!
            dfs(n-1, start, i, cost + W[cur][i])
            visited[i] = False

# 모든 도시에서 시작해본다. 딱 24가지 경우의 비용 계산
for i in range(N):
    visited[i] = True
    dfs(N-1, i, i, 0)
    visited[i] = False

print(len(costs))
print(min(costs))

 

📄 최종 제출 코드2

# 모든 도시 순회하는 경로 중 가장 작은 수

def inputValue():
    N = int(input())
    payment = []

    for _ in range(N):
        payment.append(list(map(int, input().split())))

    return N, payment

def travel_cost(startCity, curCity, cost):
    global costs, visit, cityCnt, path, totalCost

    if len(path) == cityCnt: 
        if costs[curCity][startCity] != 0:
            totalCost.append(cost + costs[curCity][startCity])
            # print(path+[startCity], cost + costs[curCity][startCity])
        return

    # 도시 갈 수있고 방문한적 없으면 방문
    for nextCity in range(cityCnt):
        if not visit[nextCity] and costs[curCity][nextCity] != 0:
            visit[nextCity] = True
            path.append(nextCity)
            travel_cost(startCity, nextCity, cost+costs[curCity][nextCity])
            visit[nextCity] = False
            path.pop()

def solution():
    global costs, visit, cityCnt, path, totalCost

    cityCnt, costs = inputValue()

    totalCost = []

    for city in range(cityCnt):
        visit = [False]*cityCnt
        visit[city] = True
        path = [city]
        travel_cost(city, city, 0)

    return min(totalCost)

if __name__ == "__main__":
    result = solution()
    print(result)