[C++] 2098번 외판원 순회 - DP, 비트마스킹, 외판원 순회

#include <iostream>
#include <algorithm>

#define LOOP(i, N) for(int i=0; i<N; i++)
#define MAX_N 17
#define FINISH ((1<<16)-1)
#define INF 987654321

using namespace std;

int N;  //도시의 개수 N
int co[MAX_N][MAX_N];  //비용: cost
int memo[MAX_N][FINISH];  //비용 최솟값 메모

void input()
{
    cin >> N;
    LOOP(i, N) {
        LOOP(j, N)
            cin >> co[i][j];
    }
}

int DP(int node, int bm)  //bitmask, start
{
    if(bm == (1<<N)-1) {
        if(co[node][0]) return co[node][0];  //다 돌았으면 처음으로 돌아가기
        else return INF;
    }
    if(memo[node][bm]) return memo[node][bm];  //메모 되있으면 쓰기
    memo[node][bm]=INF;
    
    LOOP(i, N+1) {
        int next = 1<<i;  //다음에 방문할 노드 비트
            
        if((bm&next) || !co[node][i]) continue;  //방문한 경우, 또는 길이 없는 경우
        memo[node][bm] = min(memo[node][bm], DP(i, bm|next)+co[node][i]);  //모든 경로중 최소값 넣기
    }
    return memo[node][bm];  //최종 반환하기
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    input();
    
    cout << DP(0, 1);
    
    return 0;
}

골드 1은 아직 나에게는 너무 어려운 것 같다. 골드 2까지는 그래도 할만했는데 골드 1만 되니까 난이도가 엄청 어려워진 것 같다. 이게 맞나.... 

 

첫 번재로 신경써야 할 부분이 너무 많았다. 비트 마스킹이라는 스킬도 처음 보는 거라서 맨처음에 비트연산자를 다루는 것에 상당히 애먹었었고, 그리고 이런 DP는 처음이라서 구현하는데에 많이 힘들었던 것 같다.

 

<시행착오>

1. 비트 연산자의 우선순위를 잘못 알고 있었다. >> 이 +보다 느리다니 이게 맞는지...

2. 1<<N-1을 찾는 걸 처음해봐서 오래걸렸다.

3. 경로의 최솟값을 계속 갱신하는 것이 아닌 맨처음에 가능한 모든 경로를 탐색하여 최솟값을 특정낸 후 메모리제이션 기법을 사용하여 메모리에 저장해놓고 써야됬었다.

 

 

<비트마스킹>

https://mygumi.tistory.com/361

비트마스크(BitMask) 는 무엇인가? :: 마이구미

 

<연산자 우선순위>

https://studymake.tistory.com/201

C/C++ 연산자의 우선 순위와 결합 방향

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.