[PS스터디 심화반] 3주차 백준 외판원 순회

개요

 

저희 스터디에 폭풍을 불어온 문제입니다. 개인적으로는 저희 스터디의 분기점이 된 문제라고 생각드네요.

 

 

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

2098번: 외판원 순회

 

리뷰와 피드백

 

DP문제의 난이도에 있어서 명성 익히 알며, 외판원 순회 문제가 어떠한 문제인 줄도 들어봤습니다.

저희 스터디의 한 두 명을 제외하곤 혼자서 푸는 것을 포기하였습니다.

 

외판원 순회 문제는 비트마스킹과 DP를 사용하는 어느정도 템플릿 같은 형태를 가지고 있기에

이후 DP 문제를 풀면서 큰 도움이 되었습니다.

그럼에도 이번 문제에서 사용된 재귀와 메모이제이션을 통한 시간절감이 얼마나 효과를 보는지에 대한

직관이 잘 생기지 않았으며 부족한 직관을 만회하고자 직접 그 경우를 다 따지자니 사람이 할 짓이 못 되었습니다.

 

마땅한 리뷰가 오가지 못하였고 각 자 DP 문제에 더 고뇌하는 시간만을 가졌습니다.

 

 

 

 

개선 전 / 후   코드 전문

 

 

#include <iostream>     
                        
using namespace std;    

constexpr int INF = 0x5F3F3F3F; 

                                 // 모든 도시를 한 번씩 시작점으로 둘 필요 없이
int n;  // 한 도시를 기준으로 그 기준 도시에서 다른 도시로 갈 수 있는 모든 경우(순열)로 순회하여
        // 맨마지막 도시에서 기준 도시를 갈 수 있는 경우 그 비용값을 반환한다.
int arr[18][18];  // DP의 관점으로는 기저 사례인 마지막 도시에서 기준 도시로 가는 비용은 정해져 있고
int d[18][1 << 18]; // 이 값에 마지막에 도시까지는 가는데 드는 비용을 더해서 
                    // 이번 상태에서 갈 수 있는 최소한의 비용을 저장하게 한다.
int dp(int city, int status) {
    if (status == (1 << n)-1) {
        if (arr[city][0] == 0) return INF;
        return arr[city][0];
    }

    int &cur = d[city][status]; 
    if (cur != -1) return cur;  
    
    cur = INF;  // d배열을 청므부터 INF로 초기화할 경우 재귀 단계에서 변경이 있었음을 구분할 수 없게 된다.
    for (int next = 0; next < n; ++next) {
        if (!arr[city][next]) continue; // 접근 불가 도시 경우 Pass
        if ((status & (1 << next)) == (1 << next)) continue; // 이미 상태에서 next를 포함하는 경우 Pass
            cur = min(cur, dp(next, status | 1 << next) + arr[city][next]); // 이번 상태에서 갈 수 있는 최소한의 비용을 저장
    }
    return cur;
}

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

    for (int i = 0; i < n; ++i) 
        fill(d[i], d[i]+(1 << n), -1);

    cout << dp(0, 1);
}... 생략
// 개선 후

 

 

 

 

향후 방침, 느낀 점

 

이번 문제를 통해 DP문제를 해결하는 데에 있어 시야가 조금 넓어졌다 생각이 듭니다.

 

그저 DP 문제를 해결할 땐 현재의 값이 현재의 값에서 파생된 미래의 값에 의해 결정되어질 수 있는지와

가장 먼 미래의 기저케이스에서 자신의 답을 구할 수 있는 지 등 여러가지를 고려해서

신뢰의 도약?을 하며 경험을 키워나가는 수 밖에 없나? 생각이 들었습니다.