백준 14926번 Not Equal

문제 링크입니다: https://www.acmicpc.net/problem/14926

"한 줄 표기법에 최소로 필요한 "!="의 개수인 C(N, 2)는 Vertex가 N개인 완전 그래프의 Edge의 개수와 동일함을 고려해 보라." 힌트를 보고 아래와 같이 코드를 짰습니다.

이미 방문한 간선은 다시 지나가지 않고 해당 정점에서 더 이상 이을 간선이 없다면 이전 정점으로 돌아와 간선을 이어가도록 했습니다!

*N은 홀수일 때만 가능합니다!

#include <iostream>

using namespace std;

 

const int MAX = 500 + 1;

 

int N;

//힌트: 한 줄 표기법에 최소로 필요한 "!="의 개수인 C(N,2)는

//Vertex가 N개인 완전 그래프의 Edge의 개수와 동일함

int edges[MAX][MAX]; //간선

int crossed[MAX][MAX]; //간선 지나갔는지 여부

 

void printVertex(void)

{

        int curVertex = 0;//현재 정점

                                            //마지막 간선은 항상 마지막 정점에서 1번 정점

        crossed[1][N] = crossed[N][1] = true;

        //1부터 N까지 모든 정점 지나는 간선: (N*(N-1)/2)개

        for (int i = 0; i < (N * (N - 1) / 2); i++)

        {

                 //모든 정점을 훑어본다

                 for (int vertex = 1; vertex <= N; vertex++)

                 {

                         //정점이 자기 자신이거나 이미 지나간 간선일 경우

                         if (vertex == curVertex || crossed[curVertex][vertex])

                                 continue;

                         //간선 지나갔다고 표시

                         crossed[curVertex][vertex] = crossed[vertex][curVertex] = true;

                         curVertex = vertex;

                         break;

                 }

                 cout << "a" << curVertex << " ";

        }

        //마지막 간선은 마지막 정점에서 1번 정점이므로 a1으로 끝

        cout << "a1" << endl;

}

 

int main(void)

{

        cin >> N;

 

        printVertex();

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~