TSP1 오답의 원인을 모르겠습니다.

  • faint
    faint

    제가 너무 쉽게 생각하고 코딩을 해서 그런걸까요.. 예제 입력으로 돌렸을때는 올바른 출력물이 나왔는데 제출할 때 오답이 뜹니다.

    저의 아이디어는 대략 이렇습니다.

    1) 모든 지점을 한 번씩 거치는 것으로 문제에서 N의 최대 크기로 8이 주어졌는데 8개가 주어졌을 때 탐색해야 될 경우의 수는 8!이라고 판단했습니다.

    2) 따라서 순열 알고리즘을 응용해서 만든 경로에 대한 경로값을 구한뒤 이전에 계산한 경로값과 비교해 가면서 최소 경로값을 찾아가는 방식으로 구현하고자 했습니다.

    3) 아래는 제가 제출했던 코드입니다.

    #include <iostream>
#include <cstdlib>
#include <string>

using namespace std;

int permutation[8] = { 0, 1, 2, 3, 4, 5, 6, 7 };

int factorial(int num);
void swap(double* a, double* b, double temp);
void getPath(double arr[][8], double* min, double* min_temp, int len, int start, int end);

int main()
{
    int C, N;
    double arr[8][8] = { 0.0, };
    double sum = 9999.9999;
    double sum_temp = 0.0;  
    double* min = &sum; 
    double* min_temp = &sum_temp;

    cin >> C;

    if (C > 50)
    {
        return 0;
    }

    while (C--)
    {
        for (int i = 0; i < 8; i++)
        {
            permutation[i] = i;         
            for (int j = 0; j < 7; j++)
            {
                arr[i][j] = 0.0;
            }
        }

        cin >> N;

        if (N < 3 || N > 8)
        {
            return 0;
        }

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

        getPath(arr, min, min_temp, N, 0, N - 1);

        cout << fixed;      
        cout.precision(10);     
        cout << *min << endl;
    }

    return 0;
}

int factorial(int num)
{

    if (num == 0 || num == 1)
        return 1;
    else return num * factorial(num--);
}

void swap(double* a, double* b, double temp)
{
    temp = *a;  
    *a = *b;    
    *b = temp;
}

void getPath(double arr[][8], double* min, double* min_temp, int len, int start, int end)
{
    if (start == end - 1)
    {
        *min_temp = 0.0;        
        for (int i = 0; i < len - 1; i++)
        {
            *min_temp += arr[permutation[i]][permutation[i + 1]];
        }

        if (*min > *min_temp)
            *min = *min_temp;
    }
    else
    {
        for (int i = start; i <= end; i++)
        {
            swap(permutation[i], permutation[start]);           
            getPath(arr, min, min_temp, len, start + 1, end);           
            swap(permutation[i], permutation[start]);
        }
    }
}

    애초부터 잘못된 코드인지, 탐색 방법이 부적합했는지, 예상치 못한 반례 입력값이 있는 것인지 잘 모르겠어서 도움 부탁드립니다.


    8년 전
6개의 댓글이 있습니다.
  • Being
    Being
    1. 코드가 컴파일이 되나요? swap() 함수에 인자가 안 맞는 것 같은데.. 또 permutation은 정수 배열입니다.
    2. 테스트 케이스가 여러 번 수행될 때 동작을 잘 생각해 보세요.

    8년 전 link
  • faint
    faint

    코드는 문제없이 컴파일 되며 다른 예제들로 실행했을때도 올바른 결과값을 출력합니다. swap함수 인자형 바꿔주는 것을 비롯해 기본적인 오류를 수정해도 제출 결과는 오답으로 나오네요.


    8년 전 link
  • hyunhwan
    hyunhwan

    2에 대해서는 아마 Being님께서는 아래와 같은 경우에 답이 잘못 나오는 것을 지적하고 싶으셨던 것 같습니다. 결과를 저장하는 min변수는 매 테스트 케이스에 대한 답을 구하는 과정 전에 초기화가 되어야 하는데, 올려주신 코드에는 그러한 내용이 없습니다. 확인 결과, 아래의 데이터(입력 예시를 뒤집어 넣은 경우)에 대해서 출력결과가 다르게 나오는것을 확인할 수 있었습니다.

    2
4
0.0000000000  326.0008994586  503.1066076077  290.0250922998
326.0008994586  0.0000000000  225.1785728436  395.4019367384
503.1066076077  225.1785728436  0.0000000000  620.3945520632
290.0250922998  395.4019367384  620.3945520632  0.0000000000
3
0.0000000000  611.6157225201  648.7500617289
611.6157225201  0.0000000000  743.8557967501
648.7500617289  743.8557967501  0.0000000000


    8년 전 link
  • faint
    faint

    저 댓글에서 언급을 제대로 못드렸지만 hyunhwan님께서 제시하신 부분도 이미 손을 보고 제출을 해봤습니다. 그런데도 오답이 나오니 알고리즘 자체가 잘못된게 아닌가 생각이 들기 시작합니다. 아직 어느 부분이 문제가 되는지 찾지를 못했지만..ㅠ


    8년 전 link
  • hyunhwan
    hyunhwan

    접근 방법과 순열을 이용하는 것은 맞을텐데, 지금 확인해보니 getPath함수에서 순회하는 경로의 수를 확인해보니 N!에 2배가 부족합니다. 아마 이부분에 문제가 있는것 같네요.


    8년 전 link
  • faint
    faint

    아.... 위 댓글 보고 어디가 잘못 됐는지 바로 알아챘습니다 ㅡㅡ; 뭐든지 급하게 하려다 보면 실수가 나오나 봅니다... 정말 감사합니다!


    8년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.