λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°

πŸ“ μ•Œκ³ λ¦¬μ¦˜/BOJ

[C++/BOJ] 10971 : μ™ΈνŒμ› 순회 2 (완전탐색, dfs, Backtracking)

728x90

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

문제

μ™ΈνŒμ› 순회 λ¬Έμ œλŠ” μ˜μ–΄λ‘œ Traveling Salesman problem (TSP) 라고 λΆˆλ¦¬λŠ” 문제둜 computer science λΆ„μ•Όμ—μ„œ κ°€μž₯ μ€‘μš”ν•˜κ²Œ μ·¨κΈ‰λ˜λŠ” 문제 쀑 ν•˜λ‚˜μ΄λ‹€. μ—¬λŸ¬ 가지 λ³€μ’… λ¬Έμ œκ°€ μžˆμœΌλ‚˜, μ—¬κΈ°μ„œλŠ” κ°€μž₯ 일반적인 ν˜•νƒœμ˜ 문제λ₯Ό μ‚΄νŽ΄λ³΄μž.

1λ²ˆλΆ€ν„° Nλ²ˆκΉŒμ§€ λ²ˆν˜Έκ°€ 맀겨져 μžˆλŠ” λ„μ‹œλ“€μ΄ 있고, λ„μ‹œλ“€ μ‚¬μ΄μ—λŠ” 길이 μžˆλ‹€. (길이 없을 μˆ˜λ„ μžˆλ‹€) 이제 ν•œ μ™ΈνŒμ›μ΄ μ–΄λŠ ν•œ λ„μ‹œμ—μ„œ μΆœλ°œν•΄ N개의 λ„μ‹œλ₯Ό λͺ¨λ‘ 거쳐 λ‹€μ‹œ μ›λž˜μ˜ λ„μ‹œλ‘œ λŒμ•„μ˜€λŠ” 순회 μ—¬ν–‰ 경둜λ₯Ό κ³„νšν•˜λ €κ³  ν•œλ‹€. 단, ν•œ 번 κ°”λ˜ λ„μ‹œλ‘œλŠ” λ‹€μ‹œ 갈 수 μ—†λ‹€. (맨 λ§ˆμ§€λ§‰μ— 여행을 μΆœλ°œν–ˆλ˜ λ„μ‹œλ‘œ λŒμ•„μ˜€λŠ” 것은 μ˜ˆμ™Έ) 이런 μ—¬ν–‰ κ²½λ‘œλŠ” μ—¬λŸ¬ 가지가 μžˆμ„ 수 μžˆλŠ”λ°, κ°€μž₯ 적은 λΉ„μš©μ„ λ“€μ΄λŠ” μ—¬ν–‰ κ³„νšμ„ μ„Έμš°κ³ μž ν•œλ‹€.

각 λ„μ‹œκ°„μ— μ΄λ™ν•˜λŠ”λ° λ“œλŠ” λΉ„μš©μ€ ν–‰λ ¬ W[i][j]ν˜•νƒœλ‘œ 주어진닀. W[i][j]λŠ” λ„μ‹œ iμ—μ„œ λ„μ‹œ j둜 κ°€κΈ° μœ„ν•œ λΉ„μš©μ„ λ‚˜νƒ€λ‚Έλ‹€. λΉ„μš©μ€ λŒ€μΉ­μ μ΄μ§€ μ•Šλ‹€. μ¦‰, W[i][j] λŠ” W[j][i]와 λ‹€λ₯Ό 수 μžˆλ‹€. λͺ¨λ“  λ„μ‹œκ°„μ˜ λΉ„μš©μ€ μ–‘μ˜ μ •μˆ˜μ΄λ‹€. W[i][i]λŠ” 항상 0이닀. κ²½μš°μ— λ”°λΌμ„œ λ„μ‹œ iμ—μ„œ λ„μ‹œ j둜 갈 수 μ—†λŠ” κ²½μš°λ„ 있으며 이럴 경우 W[i][j]=0이라고 ν•˜μž.

Nκ³Ό λΉ„μš© 행렬이 μ£Όμ–΄μ‘Œμ„ λ•Œ, κ°€μž₯ 적은 λΉ„μš©μ„ λ“€μ΄λŠ” μ™ΈνŒμ›μ˜ 순회 μ—¬ν–‰ 경둜λ₯Ό κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

μž…λ ₯

첫째 쀄에 λ„μ‹œμ˜ 수 N이 주어진닀. (2 ≤ N ≤ 10) λ‹€μŒ N개의 μ€„μ—λŠ” λΉ„μš© 행렬이 주어진닀. 각 ν–‰λ ¬μ˜ 성뢄은 1,000,000 μ΄ν•˜μ˜ μ–‘μ˜ μ •μˆ˜μ΄λ©°, 갈 수 μ—†λŠ” κ²½μš°λŠ” 0이 주어진닀. W[i][j]λŠ” λ„μ‹œ iμ—μ„œ j둜 κ°€κΈ° μœ„ν•œ λΉ„μš©μ„ λ‚˜νƒ€λ‚Έλ‹€.

항상 μˆœνšŒν•  수 μžˆλŠ” 경우만 μž…λ ₯으둜 주어진닀.

좜λ ₯

첫째 쀄에 μ™ΈνŒμ›μ˜ μˆœνšŒμ— ν•„μš”ν•œ μ΅œμ†Œ λΉ„μš©μ„ 좜λ ₯ν•œλ‹€.


 

λ°±μ€€ 싀버2.

Traveling Salesman Problem, μ€„μ—¬μ„œ TSP

이거 μ•Œκ³ λ¦¬μ¦˜ μˆ˜μ—…μ‹œκ°„μ— λ°°μ› λ˜ 것 κ°™μŒ

 

TSPλŠ” NP-Hard 문제의 일쒅이닀. κ°„λ‹¨νžˆ λ§ν•˜λ©΄ κ·Έλƒ₯ ν’€κΈ° μ–΄λ €μš΄ λ¬Έμ œλΌλŠ” λœ»μ΄λ‹€

 

 

main ideas

 

1. 일단 무지성 dfs...ν•˜λ©΄ λ˜λŠ”λ°, λ°±νŠΈλž˜ν‚Ήμ„ μœ„ν•΄ dfs λ‹€μŒμ— μƒνƒœλ₯Ό 기쑴으둜 λŒλ €λ†“λŠ” μ½”λ“œκ°€ μžˆμ–΄μ•Ό 함.

그리고 λͺ¨λ“  μ‹œμž‘μ μ„ κ³ λ €ν•΄μ•Όν•˜κΈ° λ•Œλ¬Έμ— 완전탐색 -> μž¬κ·€ μ§„μž…ν• λ•Œλ„ 반볡문 ν•„μš”ν•¨

 

2. λ°©λ¬Έν•˜λ €λŠ” λ‹€μŒ λ§ˆμ„μ— λ°©λ¬Έν•œμ μ΄ μžˆκ±°λ‚˜, κ°€λŠ” κ²½λ‘œκ°€ μ—†λ‹€λ©΄ continue

 

3. λ§ˆμ§€λ§‰ λ§ˆμ„μ—μ„œ μΆœλ°œμ§€λ‘œ λŒμ•„κ°ˆ 수 μžˆμ–΄μ•Ό ν•˜λ‚˜μ˜ 경둜둜 인정됨. (순회 κ°€λŠ₯)

 

4. μ΅œμ†Œκ°’μ€ μ„ μ–Έ μ‹œ INT_MAX둜 해놓고, μˆœνšŒν•˜λ©΄μ„œ μ΅œμ†Ÿκ°’μ„ μ €μž₯ν•˜κΈ°

 

 

 

λ‚˜μ˜ 풀이

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

int n;
int w[10][10] = {0};
int visited[10] = {0};
int answer = INT_MAX;

void travel(int start, int now, int cnt, int sum){
    if(cnt == n){
        if(w[now][start] == 0) return; // λ§ˆμ§€λ§‰ λ§ˆμ„μ—μ„œ μΆœλ°œμ§€λ‘œ λͺ» λŒμ•„κ°ˆλ•Œ
        if(answer > sum + w[now][start]) answer=sum+w[now][start]; // μ΅œμ†Ÿκ°’ λŒ€μ²΄
        return;
    }

    for (int i = 0; i < n; ++i){
        if(visited[i]==1 || w[now][i]==0) continue; // λ§ˆμ„λ°©λ¬Έ or κΈΈμ—†μ„λ•Œ
        visited[i] = 1;
        travel(start, i, cnt + 1, sum + w[now][i]);
        visited[i] = 0; // 탐색 μ’…λ£Œ ν›„ λ‹€λ₯Έκ²½λ‘œλ‘œ 탐색을 μœ„ν•΄ λ˜λŒλ €λ†“κΈ°
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i){
        for (int j = 0; j < n; ++j){
            cin >> w[i][j];
        }
    }

    for (int i = 0; i < n; ++i){
        visited[i] = 1;
        travel(i, i, 1, 0);
        visited[i] = 0; // λ‹€μŒ λ°˜λ³΅μ„ μœ„ν•΄ λ˜λŒλ €λ†“κΈ°
    }
    cout << answer;
}

 

728x90