[BOJ 14926] Not Equal

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

문제

주어진 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개의 수 a₁, a₂, …, a_N에 대해 가능한 한 줄 표기법 중 가장 짧으면서 사전순으로 가장 앞에 오는 한 줄 표기법을 출력하는 프로그램을 작성하라. 단 이때 "!="은 공백으로 대신하기로 한다. 예를 들어 N = 3이 주어졌을 때 "a₁ a₂ a₃ a₁"는 정답으로 인정되지만, "a₃ a₁ a₂ a₃"는 사전순으로 앞의 표기법보다 뒤에 오기 때문에 올바른 한 줄 표기법이라도 정답으로 인정되지 않는다.

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

입력

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

출력

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

제한

시간 제한	메모리 제한
1sec	512MB

---

풀이

$N$개의 수가 모두 서로 다르다는 것을 한 줄 표기법으로 나타내기 위해 필요한 최소한의 연산 횟수를 구하고, 그 경로를 사전순으로 가장 앞서게 출력하는 문제다. 문제의 힌트에서 언급되었듯, 이 문제는 $N$개의 정점을 가진 완전 그래프(Complete Graph)에서 모든 간선을 정확히 한 번씩만 지나는 경로를 찾는 문제로 치환할 수 있다.

모든 간선을 한 번씩만 지나는 경로는 오일러 경로 혹은 오일러 회로(Eulerian Circuit)라고 불린다. 그래프에서 오일러 회로가 존재하기 위한 조건은 모든 정점의 차수(Degree)가 짝수여야 한다는 것이다. 이 문제에서 $N$은 홀수로 주어지므로, 완전 그래프의 각 정점은 $N-1$개의 간선을 가지게 되어 모든 정점의 차수가 짝수가 된다. 따라서 이 그래프는 반드시 $1$번 정점에서 시작하여 다시 $1$번 정점으로 돌아오는 오일러 회로를 가진다.

해결 과정은 다음과 같다.

1. $N$개의 정점에 대해 모든 정점 쌍 사이에 간선이 존재하는 인접 행렬(grid)을 구성한다.
2. $1$번 정점(사전순으로 가장 앞서는 시작점)부터 DFS를 수행하여 오일러 회로를 탐색한다.
3. 탐색 과정에서 방문한 간선은 다시 방문하지 않도록 처리한다 ($grid[x][y] = grid[y][x] = false$).
4. 더 이상 방문할 간선이 없는 정점은 스택에 삽입하고, 탐색이 완료된 후 스택에서 역순으로 꺼내어 경로를 출력한다.

$N$의 범위는 다음과 같다.

\[1 < N < 500\]

완전 그래프의 간선 개수는 $\binom{N}{2}$개이며, $N = 499$일 때 최대 $\binom{499}{2} = 124\,251$개의 간선이 존재한다. DFS를 통한 오일러 회로 탐색의 시간 복잡도는 $O(V+E)$ 또는 인접 행렬 사용 시 $O(V^2)$이므로, 약 $250\,000$번의 연산으로 제한 시간 $1$초 내에 충분히 해결 가능하다.

소스코드

Github Link : Source Code

참고 알고리즘 : 오일러 경로