Codeforces Round #529 (Div.3) D. Circular Dance

D번) 문제 링크 : http://codeforces.com/contest/1095/problem/D

n개의 노드가 존재한다. 이 때, 순서에 상관없이 각 노드마다 자기 다음에 있는 노드 2개를 알려준다.

ex)

입력을 해석해보면

1번 노드의 뒤에는 3과 5가 오고

2번 노드의 뒤에는 1과 4

3번 노드의 뒤에는 2와 4

4번 노드의 뒤에는 1과 5

5번 노드의 뒤에는 2와 3이 온다.

이 때, 이 정보를 바탕으로 올바른 순서를 찾으면 되는 문제이다.

접근 방법은 단순하다. node라는 구조체를 만들어서 다음 값 2개를 저장한다.

그리고 set함수와 값을 하나 줬을 때 다음 값 2개 중 해당 값이 있는지를 확인하는 함수를 만든다.

다음으로 출력하는 순서는 상관없다고 했으므로 1번 노드부터 시작해서 다음 1번노드가 나올 때 까지 확인한다. 

확인하는 방법 :

1번 노드의 다음 노드 2개(편의상 a와 b라고 한다.) 모두 각각 2개의 다음 노드를 가지게 된다.

그 중 a만을 확인하여 a의 다음 노드 2개 중 b가 존재하는지 확인한다.

존재한다면, a가 1 다음인 것!

존재하지 않는다면, b가 1 다음인 것!

사실 이 문제는 노드가 3개만 존재하는 경우를 제대로 확인하지 못해서 틀렸다..T^T

+

이 문제를 푼 방법에 대해 다른 분들의 방법을 들어봤다. 처음 경우만 직접 구해주고 1번 노드를 통해 a의 다음 노드가 b라는 것이 확정된다면 a의 다음 노드 중 b가 아닌 것은 자동으로 b 다음에 오게 된다. 이런 방식으로 주루루루룩 답이 나오도록한 방법도 있었다.

세상에는 :god:들이 너무나 많다.

봤던 분들 중 가장 잘하는 것 같은 라왈리님 풀이 : http://ingu9981.blog.me/221428799679

---

- 소스코드 -

#include<iostream>
using namespace std;
struct node {
	int next1;
	int next2;
	node() {
		next1 = 0;
		next2 = 0;
	}
	void setNode(int a, int b) {
		next1 = a;
		next2 = b;
	}
	bool checkNext(int a) {
		if (next1 == a || next2 == a) {
			return true;
		}
		else {
			return false;
		}
	}
};
node arr[200002];
int main(void) {
	
	int n;
	cin >> n;
	int temp1, temp2;
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &temp1, &temp2);
		arr[i].setNode(temp1, temp2);
	}
	bool flag;
	/*
	3
	3 2
	1 3
	1 2
	*/
	int cur = 1;
	printf("%d ",cur);
	if (n == 3) {
		if (arr[arr[cur].next1].checkNext(arr[cur].next2)) {
			printf("%d %d", arr[cur].next1, arr[cur].next2);
		}
		else {
			printf("%d %d", arr[cur].next2, arr[cur].next1);
		}
	}
	else {
		if (arr[arr[cur].next1].checkNext(arr[cur].next2)) {
			cur = arr[cur].next1;
		}
		else {
			cur = arr[cur].next2;
		}
		while (cur != 1) {
			printf("%d ", cur);
			if (arr[arr[cur].next1].checkNext(arr[cur].next2)) {
				cur = arr[cur].next1;
			}
			else {
				cur = arr[cur].next2;
			}
		}
	}
}