완전 그래프는 모든 vertex가 연결돼있다.
출력하는건 사전순이다.
그래서 현재 vertex에서 사전순으로 제일 가까운것을 출력하면 된다.
그런데 N(N-1) 번째에는 1이 출력되고
N(N-2)번째에는 N이 출력된다.
이 방법을 이용하면 쉽게 풀이가능
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> | |
| /** | |
| * https://www.acmicpc.net/problem/14926 | |
| * BOJ 백준온라인져지 14926 Not Equal 풀이 | |
| */ | |
| int main(){ | |
| int N; | |
| scanf("%d", &N); | |
| N++; | |
| int **edges = new int*[N]; | |
| bool **visited = new bool*[N]; | |
| for(int i = 0; i < N; i++) edges[i] = new int[N], visited[i] = new bool[N]; | |
| int currentVertex = 0, preVertex = 0; | |
| int forLoopCount = (N - 1) * (N - 2) / 2; | |
| visited[1][N - 1] = visited[N - 1][1] = true; | |
| while(forLoopCount--){ | |
| for(int i = 1; i < N; i++){ | |
| if(i == currentVertex || visited[currentVertex][i]) continue; | |
| visited[currentVertex][i] = visited[i][currentVertex] = true; | |
| currentVertex = i; | |
| break; | |
| } | |
| printf("a%d ", currentVertex); | |
| } | |
| printf("a1"); | |
| } |
'IT > 알고리즘' 카테고리의 다른 글
| BOJ 백준온라인져지 1766 문제집 풀이 (0) | 2017.12.21 |
|---|---|
| BOJ 백준온라인져지 1005 ACM Craft 풀이 (0) | 2017.12.19 |
| BOJ 백준온라인져지 14925 목장 건설하기 풀이 (0) | 2017.12.16 |
| BOJ 백준온라인져지 14924 폰 노이만과 파리 풀이 (0) | 2017.12.16 |
| BOJ 백준온라인져지 2206 벽 부수고 이동하기 풀이 (0) | 2017.12.15 |