문제
- 팀별 작년 순위가 주어진다.
- 이번 년도에 순위가 바뀐 두 팀이 주어진다. (2, 4)일 시 만약, 팀2가 팀4보다 순위가 높았다면 이번에는 팀4가 팀2보다 순위가 높음
- 순위 변경을 확인해 이번년도 순위를 구하고 구할 수 없다면 Impossible을 출력
로직
위상정렬을 사용한다.
indegree(진입차수)가 낮을수록 높은 순위를 의미.
예를들어, 작년 순위가 5, 4, 3, 2, 1 일 때,
진입차수는 0, 1, 2, 3, 4 임을 의미한다.
또한 팀별 연결 여부를 통해 누가 더 높은 순위인지 체크한다.
예를 들어, 위와 같은 경우에서는
5 - 4, 3, 2, 1 보다 크다.
4 - 3, 2, 1 보다 크다.
3 - 2, 1 보다 크다.
2 - 1 보다 크다.
1 -
이를 true로 설정한다.
이 후, 변경된 값들을 받아 이를 변경한다.
예를 들어, (2, 4), (3, 4)를 입력받을 시 변경은 아래와 같다.
(2, 4)
그래프
4 - 1, 3
2 - 1, 4
indegree
4 - 2
2 - 2
(3, 4)
그래프
3 - 1, 2, 4
4 - 1
indgree
4 - 3
3 - 1
결과적으로
그래프
5 - {4, 3, 2, 1}
3 - {1, 2, 4}
2 - {1, 4}
4 - {1}
1 - {}
indegree
5 - 0
3 - 1
2 - 2
4 - 3
1 - 4
가 된다.
이 때, 사이클이 발생하거나 진입차수가 0이 될때 큐에 들어오는 경우가 2인경우(위상 정렬 결과가 1개가 아니라 여러개인 경우) 순위를 매길 수 없음을 의미한다.
기본적으로 indgree는 순차적으로 모두 값이 달라야한다. 하지만 indgree가 0이 되어 큐에 들어오는 팀이 여러개인 경우 순위를 매길수 없음을 의미한다.
사이클이 발생한 경우는 모든 노드를 체크하기 전에 큐가 0이된 경우를 의미한다. 이는 순차적으로 indegree를 감소 시켜도 모두 0이 되는 경우가 존재하지 않음을 의미하고 순서를 매길 수 없음을 의미한다.
예를 들어, 사이클이 발생한 경우는 2가 4보다 높고 3은 2보다 높지만 3은 4보다 낮은 경우는 사이클이 발생한다.
(사이클은 위상정렬에서 모든 노드를 체크하기전에 큐가 0이 되는 경우라고 암기해도 좋다.)
(사이클 발생 : 서로 얽혀있어 순위를 매길 수 없음)
코드
public static void main(String[] args){
// 노드의 수
int n = 5;
// 진입 차수 초기화
int[] indegree = new int[n+1];
Arrays.fill(indegree, 0);
// 연결 여부
Boolean[][] graph = new Boolean[n+1][n+1];
for(Boolean[] g : graph){
Arrays.fill(g, false);
}
// 초기 랭크
int[] data = {5, 4, 3, 2, 1};
// 초기 랭크에 따른 초기화
// indegree : 자신보다 높은 랭크 수
// graph : 노드별 연결여부 (a는 b보다 높다.)
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){
graph[data[i]][data[j]] = true;
indegree[data[j]] += 1;
}
}
int[][] lines = {
{2, 4},
{3, 4}
};
// indegree : 자신보다 높은 랭크 수 변경
// graph : 연결 방향 변경
for(int[] line : lines){
if(graph[line[0]][line[1]]){
graph[line[0]][line[1]] = false;
graph[line[1]][line[0]] = true;
indegree[line[0]] += 1;
indegree[line[1]] -= 1;
}
else{
graph[line[1]][line[0]] = false;
graph[line[0]][line[1]] = true;
indegree[line[1]] += 1;
indegree[line[0]] -= 1;
}
}
// 결과
List<Integer> result = new ArrayList<>();
// 큐
List<Integer> queue = new ArrayList<>();
// 큐 초기화
for(int i=1; i<n+1; i++){
if(indegree[i] == 0){
queue.add(i);
}
}
// 위상 정렬 결과가 여러개인 경우
Boolean certain = true;
// 사이클이 발생하는 경우
Boolean cycle = false;
for(int i=0; i<n; i++){
// 사이클 발생
// 모든 노드를 확인하기 전에 큐가 빈 경우
if(queue.size() == 0){
cycle = true;
break;
}
// 위상 정렬 결과가 여러개인 경우 발생
// 즉, 순위가 불분명한 경우
if(queue.size() >= 2){
certain = false;
break;
}
// 큐 확인
int now = queue.remove(0);
result.add(now);
for(int j=1; j<n+1; j++){
if(graph[now][j]){
indegree[j] -= 1;
if(indegree[j] == 0){
queue.add(j);
}
}
}
}
// 결과 출력
if(cycle){
System.out.println("IMPOSSIBLE");
}
else if(!certain){
System.out.println("?");
}
else{
for(int i : result){
System.out.print(i);
}
System.out.println("");
}
}
