문제 푼 날짜 : 2021-09-20

문제

문제 링크 : https://www.acmicpc.net/problem/10971

접근 및 풀이

아주 유명한 외판원 순회 문제였다.
방문하지 않았던 곳들을 방문하며, 주어진 도시들을 한 번씩 모두 방문하고 출발했던 도시로 돌아왔을 때 얼마의 비용이 들었는지 체크해주는 문제이다.
아래의 생각대로 코드를 구현하였다.

1. 각 도시에서 출발한다.
   1-1. 출발도시, 현재 방문중인 도시, 현재까지 비용, 방문한 도시의 수를 매개변수로 dfs로 방문하지 않은 도시들을 방문해준다.
2. 처음 시작한 도시로 돌아오고, 모든 도시를 방문했을 시에 비용을 업데이트해준다.

코드

// 백준 10971번 : 외판원 순회 2
#include <iostream>

using namespace std;

int N, ans = 987654321;
int arr[11][11];
bool visited[11] = { false, };

void dfs(int start, int now, int sum, int cnt) {
    if (cnt == N && now == start) {
        ans = min(ans, sum);
        return;
    }

    for (int next = 0; next < N; next++) {
        if (visited[next]) {
            continue;
        }
        if (now == next || arr[now][next] == 0) {
            continue;
        }
        visite[next] = true;
        dfs(start, next, sum + arr[now][next], cnt + 1);
        visited[next] = false;
    }
}

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

    cin >> N;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
        }
    }
    for (int row = 0; row < N; row++) {
        dfs(row, row, 0, 0);
    }
    cout << ans;
    return 0;
}

결과

피드백

백트래킹을 공부하는 데에 있어서 아주 좋은 문제였던 것 같다.