ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 백준(Baekjoon)문제 풀이 - 3665 최종 순위(C++)
    PS(알고리즘 문제풀이) 관련 글/백준(Baekjoon)풀이 2024. 3. 5. 21:38

    최종 순위

    문제

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

    원래 등수와 서로 바뀐 등수가 출력 되었을 때의 새로운 등수를 출력하는 문제이다. 만약 확실하지않다면 "?" , 데이터의 일관성이 없어 오류가 발생하는 경우에는 "IMPOSSIBLE"을 출력한다.

    입출력 형식

    <입력 형식>

    팀의 수 n을 포함하고 있는 한 줄. (2 ≤ n ≤ 500)

    n개의 정수 ti를 포함하고 있는 한 줄. (1 ≤ ti ≤ n) ti는 작년에 i등을 한 팀의 번호이다. 1등이 가장 성적이 높은 팀이다. 모든 ti는 서로 다르다.

    상대적인 등수가 바뀐 쌍의 수 m (0 ≤ m ≤ 25000)

    두 정수 ai와 bi를 포함하고 있는 m줄. (1 ≤ ai < bi ≤ n) 상대적인 등수가 바뀐 두 팀이 주어진다. 같은 쌍이 여러 번 발표되는 경우는 없다.

     

    <출력 형식>

    n개의 정수를 한 줄에 출력한다. 출력하는 숫자는 올해 순위이며, 1등팀부터 순서대로 출력한다. 만약, 확실한 순위를 찾을 수 없다면 "?"를 출력한다. 데이터에 일관성이 없어서 순위를 정할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

     

    <입력 예>

    3
    5
    5 4 3 2 1
    2
    2 4
    3 4
    3
    2 3 1
    0
    4
    1 2 3 4
    3
    1 2
    3 4
    2 3

     

    <출력 예>

    5 3 2 4 1
    2 3 1
    IMPOSSIBLE

     

    아이디어

     위상정렬 문제이다. 다만 바뀐 등수와 처음등수를 통한 새로운 노드들을 어떻게 처리하는지가 관권이 되는 문제라고 생각한다.

    우선 출력 형식이 3가지로 나뉨으로 우리도 3가지로 나누어 생각해보자.

     

    - "?"가 출력되는 경우 : 순서가 불확실한 경우, 즉 한노드에서 진입차수를 지웠을 때, 진입차수가 0인 노드가 2개이상이라면, 순서가 불확실 함으로 "?"를 출력

    - "IMPOSSIBLE"을 출력하는 경우 : "IMPOSSIBLE"을 출력하는 경우는 아예 위상정렬이 되지않는 그래프일때 즉, 싸이클이 존재하는 경우이다.

    - 모두 아니라면 정상적으로 바뀐 순위를 출력하면 된다.

     

    이렇게 출력 형식별로 경우를 나누어 보았다. 이제 처음등수와 바뀐 새로운 노드들을 어떻게 처리해야하는지를 알아봐야 한다. 우선 노드에 해당하는 순서를 서로 바꾸기 편하도록 인접리스트가 아닌 인접 행렬을 이용하여 구현하는 것이 좋아보인다. 우선 순위를 순서대로 입력받은 뒤, 자신보다 높은 등수의 노드를 모두 추가하여 준다. 즉 아래와 같다.

     

    <순위 별 연결 리스트>

    1위 : -

    2위 : 1위 노드

    3위 : 1위 노드, 2위 노드

    4위 : 1위 노드, 2위 노드, 3위 노드

    .

    .

    .

    N위 : 1위 노드, 2위 노드, ....., N-1위 노드

     

    위와 같이 연결 관계를 인접 행렬로 만든 후, 주어진 두수의 순서를 서로 바꾼 뒤, 위상 정렬을 돌려주면 된다.

     

    ※싸이클은 모든노드를 확인하지 않았을 때, queue가 먼저 비어버리면 발생한다.

    ※초기화해야할 변수가 매우 많으니 초기화를 주의하자.

     

    <소스 코드>

    더보기
    #include <stdio.h>
    #include <algorithm>
    #include <vector>
    #include <queue>
    
    using namespace std;
    
    int n, rk[510], ent[510];
    int arr[510][510];
    int m, ch[510];
    int check = 0;
    
    int main()
    {
    	int i, j;
    	int t;
    	scanf("%d", &t);
    	while (t--) {
    		scanf("%d", &n);
    		for (i = 1; i <= n; i++) scanf("%d", &rk[i]);
    		for (i = 1; i <= n; i++) {
    			for (j = 1; j < i; j++) {
    				arr[rk[i]][rk[j]] = 1;
    				ent[rk[j]]++;
    			}
    		}
    		scanf("%d", &m);
    		for (i = 0; i < m; i++) {
    			int x, y;
    			scanf("%d %d", &x, &y);
    			if (arr[x][y] == 1) {
    				arr[x][y] = 0;
    				arr[y][x] = 1;
    				ent[y]--;
    				ent[x]++;
    			}
    			else if (arr[y][x] == 1) {
    				arr[y][x] = 0;
    				arr[x][y] = 1;
    				ent[x]--;
    				ent[y]++;
    			}
    		}
    		queue <int> q;
    		for (i = 1; i <= n; i++) {
    			if (ent[i] == 0) {
    				ch[i] = 1;
    				q.push(i);
    			}
    		}
    		int cnt = 0;
    		vector<int> ans;
    		while (!q.empty()) {
    			int now = q.front();
    			q.pop();
    			ans.push_back(now);
    			for (i = 1; i <= n; i++) {
    				if (arr[now][i] == 1) {
    					ent[i]--;
    					if (ent[i] == 0) {
    						q.push(i);
    						ch[i] = 1;
    						cnt++;
    					}
    				}
    			}
    			if (cnt > 1) check = 2;
    		}
    		for (i = 1; i <= n; i++) if (ch[i] == 0) check = 1;
    		if (check == 1) printf("IMPOSSIBLE\n");
    		else {
    			for (i = ans.size() - 1; i >= 0; i--) printf("%d ", ans[i]);
    			printf("\n");
    		}
    		for (i = 0; i <= n; i++) {
    			for (j = 0; j <= n; j++) {
    				arr[i][j] = 0;
    			}
    		}
    		for (i = 0; i <= n; i++) ent[i] = 0, ch[i] = 0, rk[i] = 0;
    		check = 0;
    		ans.clear();
    	}
    	return 0;
    }

     

Designed by Tistory.