글 읽기 - (1199번 - 오일러 회로) 어떤 예외가 있는지 잘 모르겠습니다.

kordreamfollower 9년 전 0

간선의 상태를 받아서, 간선 하나하나를 지워나가며 DFS탐색을 시도합니다.

탐색 전에 각 노드마다 연결된 간선의 갯수가 전부 짝수개인지 확인하고 아닐 경우 -1 출력하고 종료합니다.

DFS탐색을 하여 간선을 전부 지웠을 경우 다 돌은것으로 판단하여 해당 경로를 출력하고 종료하도록 코딩을 하였습니다.

DFS탐색을 하면서 들어가다가 아닌 경로로 들어가면 다시 되돌아나와 지웠던 경로를 다시 복원하고 다른 경로로 들어가도록 되어 있습니다.

그런데 어디서 틀렸는지 잘 모르겠습니다. 직접 테스트케이스 몇 개를 만들어서 넣어봤는데 잘 모르겠네요.

(혹시 자기 자신으로 가는 경로가 존재하나요?)

#include <iostream>
#include <vector>

using namespace std;

void process(int N, bool **Grid, int count);
void DFS(int N, bool **Grid, int point, int count, vector<int> List);

int main(void)
{
    int N;
    cin >> N;
    
    int count = 0;
    
    bool **Grid = new bool*[N + 1];
    for(int i = 1; i <= N; i++)
    {
        Grid[i] = new bool[N + 1];
        for(int j = 1; j <= N; j++)
        {
            cin >> Grid[i][j];
            if(Grid[i][j])
                count++;
        }
    }
    
    count /= 2;
    process(N, Grid, count);
    
    return 0;
}

void process(int N, bool **Grid, int count)
{
    vector<int> List;
    
    for(int i = 1; i <= N; i++)
    {
        int check = 0;
        for(int j = 1; j <= N; j++)
        {
            if(Grid[i][j])
                check++;
        }
        
        if(check % 2 != 0)
        {
            cout << -1 << endl;
            return;
        }
    }
    
    for(int i = 1; i <= N; i++)
    {
        List.push_back(i);
        DFS(N, Grid, i, count, List);
        List.pop_back();
    }
}

void DFS(int N, bool **Grid, int point, int count, vector<int> List)
{
    if(List.size() == count + 1 && point == List[0])
    {
        for(int i = 0; i <= count; i++)
            cout << List[i] << " ";
        cout << endl;
        exit(0);
    }
    
    for(int i = 1; i <= N; i++)
    {
        if(Grid[point][i])
        {
            Grid[point][i] = false;
            Grid[i][point] = false;
            List.push_back(i);
            
            DFS(N, Grid, i, count, List);
            
            List.pop_back();
            Grid[point][i] = true;
            Grid[i][point] = true;
        }
    }
}

Nada 9년 전 1

입력의 조건에 두 정점 사이에 간선이 여러 개 있을 수 있습니다.

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

문제

문제

출처

ICPC

(1199번 - 오일러 회로) 어떤 예외가 있는지 잘 모르겠습니다.

kordreamfollower 9년 전 0

Nada 9년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말