글 읽기 - 2098 외판원 순회 알고리즘 질문있습니다.

koko514 5년 전 0

외판원 순회 알고리즘이 궁금하여 찾아보았습니다.

답에 가장 관련있는 부분은 지웠구요..

궁금한 것은 문제는 어느 한 도시에서 출발하여 다시 그 도시에 도착하는데에 최소 비용을 요구하는데 이 코드는 0 도시에서 시작하여 0 도시로 오는데의 최솟값을 구한거 아닌가요?

정답자 코드 보았는데 대부분 cur이 0에서 시작하여 다 방문하면 city[cur][0]을 return하던데 이것이 어떻게 최솟값이 될 수 있는지가 궁금합니다.

#include <iostream>
#include <algorithm>
 #define MAX_NUM 987654321
 using namespace std;
 int city[16][16];
int cache[16][65536];
 int num;
 int tsp(int cur, int visited) {
   // 다 방문 했다면
    if (visited == (1 << num) - 1) {
        return city[cur][0];
    }
     int & ret = cache[cur][visited];
 // 메모이제이션 반환
    if (ret != 0) {
        return ret;
    }
    ret = MAX_NUM;
    for (int i = 0; i < num; i++) {
        // 방문했으면 패스
        if (visited & (1 << i))
            continue;
        // 갈 수 없는 길이라면 패스
        if (city[cur][i] == 0)
            continue;
       // ret 의최솟값 메모제이션
    }
    return ret;
}
 int main()
{

    cin >> num;
 
    for (int i = 0; i < num; i++) {
        for (int j = 0; j < num; j++) {
 
            cin >> city[i][j];
 
        }
    }
    cout << tsp(0, 1);
 
}

onjo0127 5년 전 0

외판원이 모든 도시를 정확히 한 번씩 방문한다는 점을 잘 생각해보면, 어느 도시에서 출발했던 간에 항상 같은 답이 나온다는 걸 알 수 있습니다.

koko514 5년 전 0

죄송합니다만 1번부터 5번까지 노드가 5개 있다고 치면, 1 - 2 - 3 - 4 -5 - 1 와 2- 1 - 3 - 4 - 5 - 2 가 단방향 그래프니까 서로 다른값 을 가지지 않나요? 따라서 최솟값도 모든 노드에대해서 다 구해야 되는거 아닌가요?

koko514 5년 전 1

해결했습니다. 감사합니다.!

sotter1020 5년 전 0

저도 이거 궁금한데.. 해결하셨으면 알려주시면 안될까요?

저도 처음에 모든 노드가 출발했을 경우를 생각해서 코드를 짰는데..

메모제이션 크기에서 문제가 생겨 고생좀 했다가 이 관점에서 보고 풀었는데 맞긴했거든요..

근데 왜 어느 정점에서 출발하든 최소값이 나오는지 잘 모르겠습니다..

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2098 외판원 순회 알고리즘 질문있습니다.

koko514 5년 전 0

onjo0127 5년 전 0

koko514 5년 전 0

koko514 5년 전 1

sotter1020 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말