[백준 BOJ 3665 gold1 - 최종 순위] 위상정렬(topological sort) C++

 

백준 3665 최종 순위

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

3665번: 최종 순위

 

위상정렬 문제이다. 

2차원 배열에 edge를 저장하는 방식으로 풀었다. 

 

			int nf, nt;
			cin >> nf >> nt;
			/*if (adj[nt][nf] == 1) {
				adj[nt][nf] = 0;
				indegree[nf]--;
			}
			adj[nf][nt] = 1;
			indegree[nt]++;*/
			if (adj[nf][nt]) {
				adj[nf][nt] = 0;
				adj[nt][nf] = 1;
				indegree[nt]--;
				indegree[nf]++;
			}
			else {
				adj[nt][nf] = 0;
				adj[nf][nt] = 1;
				indegree[nf]--;
				indegree[nt]++;
			}

 

작년 순위에서 상대적인 순위가 바뀐 팀의 목록이 조건으로 주어진다. 

예시에서

'예를 들어, 작년에 팀 13이 팀 6 보다 순위가 높았는데, 올해 팀 6이 팀 13보다 순위가 높다면, (6, 13)을 발표할 것이다.' 만 보고 , 주석 처럼 코드를 작성해서 틀렸다. 

 

 

- 데이터에 일관성이 없어서 순위를 정할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

-> 위상정렬 그래프에서 사이클이 있다는 것을 의미한다. 사이클이 있다는 것을 코드상에서 아는 방법은 queue에 아무 것도 들어가지 않을 때이다. 즉, indegree가 0인 노드가 없는 것이다. 

 

- 확실한 순위를 찾을 수 없다면 "?"를 출력한다.

-> indegree 가 0 인 노드를 먼저 탐색하는데, 이런 노드가 여러 개 일때를 의미한다. 큐의 사이즈가 2 이상이라면 ?를 출력한다.