백준 문제 14926번 Not Equal 문제풀이 c++

https://www.acmicpc.net/problem/14926

14926번: Not Equal

 

문제해석

이 문제 이해하기가 좀 어려웠다.

 

Hint : 한 줄 표기법에 최소로 필요한 "!="의 개수인 C(N, 2)는 Vertex가 N개인 완전 그래프의 Edge의 개수와 동일함을 고려해 보라.

 

이 힌트가 큰 도움이 되었다.

만약 이 힌트가 없었다면 못풀었거나 그래프 그래보고 이 특성을 찾는데 시간이 굉장히 걸렸을 것이다.

 

힌트를 바탕으로 정점개수가 5인경우 한번만 그려보고 바로 제출했더니 맞았다.

 

한마디로 한붓그리기를 하면된다.

사전 순으로 가장 앞에 오는것을 출력해야하므로 선택가능한것중 제일 작은 정점번호를 선택하면된다.

선택 가능하다의 조건이 있는데 나를 가리키는 것 + 내가 가리키는것<n-2여야한다.

 

위 그림에서 초록색 6번 다음 a5에서 선택 할 수있는것중 가장작은것은 a1이지만 초록 6까지 진행한 상태에서 a1는 a2와 a4를 가리키고있고 a3이 a1을 가리키고 있어 총 3개가되고 3<3 이 아니므로 a1다음으로 작은것인 a2를 보고 선택 할수 있는가를 판단 후 선택 할 수 있으므로 a2를 선택한것이다.

무엇보다 6번 다음 a5가 a1을 선택하면 나가는 길이없어서 한붓 그리기가 안된다.

 

한붓그리기하면 dfs를 떠올리는것이 어렵지않으므로 그렇게 작성하였다.

 

코드

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void dfs(int start,int depth);
bool graph[500][500];
int cnt[500];
int n;
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>n;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(i!=j)
            {
                graph[i][j]=1;
            }
        }
    }
    dfs(0,0);
    cout<<"a1";
}
void dfs(int start,int depth){
    cout<<"a"<<start+1<<" ";
    if(depth==n*(n-1)/2)
    {
        return;
    }
    for(int i=0; i<n; i++)
    {
        if(graph[start][i]==1&&cnt[i]<n-2)
        {
            cnt[start]++;
            cnt[i]++;
            graph[start][i]=0;
            graph[i][start]=0;
            dfs(i,depth+1);
        }
    }
}