[BOJ/백준] 10971 외판원 순회 2

● [문제번호 10971] 10971 외판원 순회 2

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

10971번: 외판원 순회 2

 

● 알아야 할 것

: DFS

: 재귀

 

● 풀이 과정

: 순열을 가지고 요리조리 하는 것 같아 고민을 많이 했다.

그러다가 하드코딩해서 구현을 했는데, '시간 초과' 가 나왔다.

 

왜 그런지 고민을 해보니 중복되는 부분이 많았다.

왜냐하면 구하고자하는 값에는 같은 사이클들 중 순서가 필요없다.

예를 들어, 0123 , 1230, 2301, 3012 모두 같은 값이 나온다.

따라서 0행에서만 시작을 해주면 중복없이 된다.

(방문하는 도시의 개수 : N개 / 비용 횟수(금액X) : N+1)

 

1. 0행에서 {다음 도시로 가는 비용이 0이 아니라는 조건을 만족하고} 다음 도시로 이동

 

2. 방문했으니 비용 저장

 

3. (Base Case) 방문한 도시가 N-1 개 인 경우

→ 왜냐하면 처음 도시로 돌아가기 전 마지막 방문도시에서 visited의 모든 원소는 true이다.

 

3-1. 처음 도시로 돌아가는 비용을 포함하여 총 비용 구하기

3-2. {총 비용} < {현재까지 구한 최소 비용} 인 경우 저장

 

4. 현재 도시 방문 체크인

 

5. 조건에 맞는 가능한 다음 도시로 재귀

5-1. (조건1) 자기 자신의 도시로 돌아가지 않는 경우 ('대각성분 : 행==열' 이 아닌 경우)

5-2. (조건2) 다음 도시로 가는 비용이 0이 아닌 경우

5-3. (조건3) 다음 도시가 방문한 적 없는 경우

 

6. 현재 도시 방문 체크아웃

 

● 주의 할 것

: 비용을 저장한 배열이 2차원으로 되어 있고,

방문한 도시의 비용 저장 배열(num), 방문한 도시 표시 배열(visited) 의 index들을 집중해서 주의해야한다.

 

● 참고 할 것

: NULL

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// cost : from 도시에서 to 도시로 이동하는데 필요한 비용
// num : 방문한 도시의 비용을 순서대로 저장
// visited : 방문한 도시를 표시 (true : 방문 / false : 미방문)
int cost[10][10] = {0, };
int num[10] = {0, };
bool visited[10] = {false, };
int N, sol = 10000000;

void TSP(int from, int to, int cnt, int home)
{
    // 방문했으니 비용 저장
    num[cnt++] = cost[from][to];
    
    // 방문한 도시가 N-1 개 인 경우
    if(cnt == N - 1)
    {
        // 처음 시작한 도시로 가는 비용이 0이 아닌 경우
        if(cost[to][home] != 0)
        {
            // 처음 시작한 도시로 돌아가는 비용 추가
            num[cnt] = cost[to][home];
            
            // 총 비용 구하기
            int total = 0;
            for(int i = 0; i < N; i++)
                total += num[i];
            
            // '총 비용'이 현재까지 최소 비용 보다 작은 경우
            if(total < sol)
                sol = total;
        }
        
        return ;
    }
    
    // 가능한 다음 도시로 이동
    for(int i = 0; i < N; i++)
    {
        // 현재 도시 방문 체크인
        visited[from] = true;
        
        // 다음 도시로 못 가는 경우
        // 1. 자기자신의 도시로 가는 경우 (대각성분 : 행==열)
        // 2. 다음 도시로 가는 비용이 0 인 경우
        // 3. 다음 도시가 방문한 적 있는 경우
        if(to != i && cost[to][i] != 0 && !visited[i])
            TSP(to, i, cnt, home);
        
        // 현재 도시 방문 체크아웃
        visited[from] = false;
    }
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    // 각 도시 이동 비용 입력
    for(int a = 0; a < N; a++)
        for(int b = 0; b < N; b++)
            cin >> cost[a][b];
    
    // 제자리로 오는 순회를 하는 것이기에 (한붓그리기)
    // 출발을 0행에서만 진행해도 된다
    for(int a = 1; a < N; a++)
        // 0도시에서 다음 도시로 가는 비용이 0이 아닌 경우
        if(cost[0][a] != 0)
            TSP(0, a, 0, 0);
    
    cout << sol;
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [520 - 브루트 포스 - 순열] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	10972	다음 순열	https://pirateturtle.tistory.com/237
2	10973	이전 순열	https://pirateturtle.tistory.com/238
3	10974	모든 순열	https://pirateturtle.tistory.com/239
4	10819	차이를 최대로	https://pirateturtle.tistory.com/240
5	10971	외판원 순회 2	https://pirateturtle.tistory.com/241
6	6603	로또	https://pirateturtle.tistory.com/242