[BOJ] 14926 - Not Equal

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

 

BOJ - Not Equal

문제 유형: 오일러 경로, 그래프, dfs, 그리디, 백트래킹

문제 난이도: Gold V

시간 제한: 1초

메모리 제한: 512MB

 

문제

주어진 N개의 수가 모두 서로 다르다는 것은 기호 "!="를 통해 하나의 식으로 표현할 수 있다. 예를 들어 A, B, C가 모두 서로 다르다는 것은 논리식으로 (A != B) && (B != C) && (C != A) 로 쓸 수 있고, 이를 다음과 같이 한 줄로 표현하는 것을 A, B, C에 대한 "한 줄 표기법"이라고 부르기로 하자.

A != B != C != A

하지만 5개의 수 A, B, C, D, E가 모두 서로 다르다는 것을 다음처럼 표현하는 것은 올바른 한 줄 표기법이 아니다.

A != B != C != D != E

왜냐하면 5개의 수가 서로 다름을 나타내기 위해서는 10개의 쌍에 대해 서로 다름을 표현해야 하고, 이는 적어도 10개의 "!="를 필요로 하기 때문이다. 일반적으로 주어진 N개의 수가 모두 다름을 한 줄 표기법으로 표현하기 위해서는 적어도 C(N, 2)개의 "!="이 필요함이 알려져 있다(C(N, 2) : N개의 서로 다른 대상 중 2개를 뽑는 가짓수).

홀수 자연수 N이 주어졌을 때, N개의 수 a1, a2, …, aN에 대해 가능한 한 줄 표기법 중 가장 짧으면서 사전순으로 가장 앞에 오는 한 줄 표기법을 출력하는 프로그램을 작성하라. 단 이때 "!="은 공백으로 대신하기로 한다. 예를 들어 N = 3이 주어졌을 때 "a1 a2 a3 a1"는 정답으로 인정되지만, "a3 a1 a2 a3"는 사전순으로 앞의 표기법보다 뒤에 오기 때문에 올바른 한 줄 표기법이라도 정답으로 인정되지 않는다.

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

 

입력

첫째 줄에 자연수 N이 주어진다. N은 1보다 크고 500보다 작은 홀수이다.

 

출력

첫째 줄에 가능한 한 줄 표기법 중 가장 짧으면서 사전순으로 가장 앞에 오는 것을 출력한다.

 

풀이

간선이 n*(n-1)/2개이므로, n*(n-1)/2+1번 방문해야 한다.

처음에 1부터 시작해서, 사전순 가장 앞에 오는 것이므로, 앞쪽 번호 우선으로 백트래킹을 하여 성공시 출력하고 빠져나온다.

방문처리를 하면서 양방향 간선을 추가해주면서 구현해주면 된다.

백트래킹 성공의 기준은 남은 설치간선수가 0인 경우이다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int n;
bool adj[501][501];
short seq[501 * 501];

bool dfs(int node, int left) {
    if (left == 0) {
        for (int i = n * (n - 1) / 2; i >= 0; i--) {
            cout << "a" << seq[i] << " ";
        }
        cout << "\n";
        return true;
    }

    for (int i = 1; i <= n; i++) {
        if (!adj[node][i]) {
            adj[node][i] = true;
            adj[i][node] = true;
            seq[left - 1] = i;
            if (dfs(i, left - 1)) {
                return true;
            }
            seq[left - 1] = 0;
            adj[node][i] = false;
            adj[i][node] = false;
        }
    }

    return false;
}

int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        adj[i][i] = true;
    }

    seq[n * (n - 1) / 2] = 1;
    dfs(1, n * (n - 1) / 2);

    return 0;
}