취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 14926번 문제인 Not Equal이다.
문제는 아래 링크를 확인하자.

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

a1, a2, ..., an의 총 N개의 노드로 이루어진 완전그래프를 생각해보면, ai들이 서로 다르다는 것을 논리식으로 나타내기 위해서는 해당 완전그래프의 각각의 에지에 대응되는 논리식이 적혀있어야 한다.

a1 an을 잇는 에지를 지운 완전그래프에서, 사전순으로 가장 빠른 a1에서 an으로 가는 오일러 경로를 출력한 후 마지막으로 an에서 a1으로 가는 에지를 출력해주자.

위 그래프의 오일러경로는 각 노드에서 사전순으로 접근할 수 있는 가장 빠른 노드를 출력하는 것으로 구할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int idx[500];
bool chk[500][500];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	for (int i = 1; i <= N; i++) chk[i][0] = chk[i][i] = 1;
	chk[1][N] = chk[N][1] = 1;
	int cnt = N * (N - 1) / 2;

	cout << "a1";
	int cur = 1;
	for (int i = 1; i < cnt; i++) {
		int& idxcur = idx[cur];
		while (chk[cur][idxcur]) idxcur++;
		chk[cur][idxcur] = chk[idxcur][cur] = 1;
		cur = idx[cur];
		cout << ' ' << 'a' << cur;
	}

	cout << ' ' << "a1";
}