7-A 질문

강의를 안보고 처음 짠 코드에서 무엇이 잘못됬는지 몰라서 답답해서 질문드립니다.

이 코드의 반례를 알 수 있을까요? 혹은 어느 부분이 틀렸는지입니다.

#include <iostream>
#include <cstring>
#include <climits>
#include <algorithm>

using namespace std;

int n;
int dp[20][20][20];
int w[20][20];
int visit[20];


//bidx == 시작한 처음 위치
void search(int cnt, int from, int dist, int bidx) {

    if (cnt == n - 1 && w[from][bidx] > 0) {
        int nd = dist + w[from][bidx];
        if (dp[from][bidx][cnt] < nd) return;
        dp[from][bidx][cnt] = nd;

        return;
    }

    for (int i = 0; i < n; ++i) {
        if (from == i || visit[i] || w[from][i] == 0) continue;

        int nd = dist + w[from][i];
        if (dp[from][i][cnt] > nd) {
            dp[from][i][cnt] = nd;
            visit[i] = 1;
            search(cnt + 1, i, nd, bidx);
            visit[i] = 0;
        }
    }
}

int main() {
    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)
        for (int j = 0; j < n; ++j)
            for (int k = 0; k < n; ++k) dp[i][j][k] = INT_MAX;

       for (int i = 0; i < n; ++i) {
            memset(visit, 0, sizeof(visit));
            visit[i] = 1;
            search(0, i, 0, i);
    }

    

    int answer = INT_MAX;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            answer = min(answer, dp[i][j][n - 1]);
            // cout << dp[i][j][n - 1] << " ";
        }
        // cout << "\n";
    }
    cout << answer;
    return 0;
}

접근 방법은 3차원 dp를 dfs로 탐색한 거리를 저장해두는 것입니다. 그래서 다음에 같은 dp[from][to][cnt] 가 존재할 때, 반드시 새로운 값이 낮을 때만 재귀를 수행하게 됩니다.

재귀 끝내는 파트인 cnt == n- 1에서는 모든 노드를 순회했고 시작부분을 더하기 위해 w[from][bidx] 가 0이 아닌 경우에만 값을 구하게 됩니다.

그래서 마지막 dp[][][n-1] 중 가장 작은 값을 정답으로 가져옵니다.

백준 질문하기에서 대부분 반례를 시도해보고 디버깅도 시도해봤는데 뭐가 잘못됬는지 알기 어려워 답답한 마음에 질문드립니다.

안녕하세요 밥먹는 아이님 ㅎㅎ

일단 이코드요.

void search(int cnt, int from, int dist, int bidx) {

    if (cnt == n - 1 && w[from][bidx] > 0) {
        int nd = dist + w[from][bidx];
        dp[bidx][bidx][cnt] = min(dp[bidx][bidx][cnt], nd); 
        return; 
    }

이렇게 되어야 맞는 의미아닐까요? 결국 0 ~ 0, 1 ~ 1 이런 값들을 DP에 담아놓으려고 하는것 아닌가요?

또한,

마지막에 이러한 값들을 대상으로

    int answer = INT_MAX;
    for (int i = 0; i < n; ++i) { 
        answer = min(answer, dp[i][i][n - 1]); 
    }

이것만 answer에 담는게 올바른 게 아닐까요? 우리는 i ~ j까지의 최소값이 아니라 i ~ i까지의 최솟값을 구하는거니까요.

근데 이렇게 고쳐서 제출해도 2%에서 틀렸다고는 뜨긴 합니다만... 애초에 이 코드가 메모이제이션도 안 걸어져있어서 시간초과가 날 거 같은데요. 혹시 이 부분은 고려하셨나요??

이 문제의 최대범위는 16이기 때문에 16!이 되어서, 이정도의 최대시간복잡도(20922789888000), 약, 20조의 시간복잡도를 가지는 코드라서 메모이제이션 거는 DP로 하셔야 할 것 같아요

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

인프런 커뮤니티 질문&답변