[BOJ - 10971] 외판원 순회 2(C++)

문제

 

접근방법

• 1 ~ N번까지 도시에 번호가 매겨짐(코드 구현시에 0 ~ N-1로 구현해야겠다 구상)
• W[현재위치][이동위치]의 값이 0인 경우 이동 불가능 -> 조건으로 처리
  • how? -> 백트래킹으로 접근
• 초기 설정에서 visited[0]을 true로 처리(이미 0에서 시작한다고 가정)
  • 마지막 조건에서 현재 위치에서 0으로 이동 가능한 경우의 dist를 min_dist와 비교하며 갱신

 

코드

#include <iostream>
#include <vector>

using namespace std;
#define INF 1e9

int N;
vector<vector<int>> W;
vector<bool> visited;
int min_dist = INF;

void dfs(int pos, int dist, int cnt) {
    if (cnt == N-1) {
        if (W[pos][0] == 0) return;

        dist = dist + W[pos][0];
        min_dist = min(min_dist, dist);
        return;
    }

    for (int i = 1; i < N; i++) {
        if (visited[i] || W[pos][i] == 0) continue;

        visited[i] = true;
        dfs(i, dist + W[pos][i], cnt + 1);
        visited[i] = false;
    }
}

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

    cin >> N;

    W.resize(N, vector<int>(N));
    visited.assign(N, false);

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

    visited[0] = true;
    dfs(0, 0, 0);

    cout << min_dist;

    return 0;
}

 

리팩토링(??)

• 지교수님께서 변수 이름을 좀 더 명확하게 설정하는 것 외에는 없다고 하셔서 너무 만족스럽네요,, 하핳

 

링크

10971번: 외판원 순회 2