Q45. 최종 순위

3665번: 최종 순위 (acmicpc.net)

3665번: 최종 순위

 

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

아니 문제가..

뭐이리 어려웤ㅋㅋㅋㅋㅋㅋ

왠지 위상정렬문제일거같은데.. 일단 생각좀 해보자 ㅋㅋ ㅠ

 

IMPOSSIBLE을 출력하는 경우는 topology sort에서 cycle이 발생한 경우일거같고 ?을 출력해야 되는 경우는 topology sort 도중 indegree가 0인 노드가 여러개 있을 경우일거같다. 

 

일단 작년순위에 대한 그래프는 그냥 일자로 쭉 그리면 된다

a b c 순위였으면

a -> b -> c 로 그래프를 만들면 위상정렬 했을때 순위그대로 나오니까.

근데 올해 변경된 순위에 대해서 (a,c)라고 치면 c에서 a로 가는 간선이 생겨야되는데 그럼 사이클이 생겨버린다. 순위가 바뀌었으니까 기존에 있던 간선을 좀 제거하거나 뭐 어떻게 처리를 해야될거같은데 이부분을 어떻게 해야될지 모르겠네 이것만 해결되면 발상 끝인데 ㅠ

 

정답 볼까말까...

아 그냥 이해가 안된다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ 내 머리로는.. 하 ㅋㅋ

 

(정답봤음)

어? 아..

작년 순위 주어지면 a -> b -> c 이런식으로 일렬로 그래프를 만드는게 아니구나..;;;;;

a->b

a->b

b->c

순위가 높은 팀에서 자기보다 순위 낮은 팀에 간선이 다 이어져야 되네.. 아...

아ㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏ

알듯말듯 한 거였는데 왜 발상을 못했지 확실하게;; 아ㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏ

아ㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏ

 

일단 내가 첨에 생각한 이부분은 맞았다

"IMPOSSIBLE을 출력하는 경우는 topology sort에서 cycle이 발생한 경우일거같고 ?을 출력해야 되는 경우는 topology sort 도중 indegree가 0인 노드가 여러개 있을 경우일거같다. "

 

작년 순위를 그래프로 표현하는 부분만 발상했으면 이 문제는 식은죽먹기였다

젠장 아깝구먼

 

아 그리고 N이 크지 않아서 인접행렬로 그래프를 표현할 수 있다~!!!

앞으로 그래프문제 보면 인접행렬 쓸수있는지 없는지부터 봐야긋네

 

 

from collections import deque

for test_case in range(int(input())):
    N = int(input())
    prev_rank = list(map(int, input().split()))
    graph = [[False] * (N + 1) for _ in range(N + 1)]
    indegree = [0] * (N + 1)

    for i in range(N):
        for j in range(i + 1, N):
            graph[prev_rank[i]][prev_rank[j]] = True
            indegree[prev_rank[j]] += 1

    M = int(input())
    for _ in range(M):
        a, b = map(int, input().split())
        graph[a][b] = not graph[a][b]
        graph[b][a] = not graph[b][a]
        if graph[a][b]:
            indegree[b] += 1
            indegree[a] -= 1
        else:
            indegree[a] += 1
            indegree[b] -= 1
        
    q = deque()
    for i in range(1, N + 1):
        if indegree[i] == 0:
            q.append(i)
    
    impossible = False
    ambiguous = False
    result = []

    for i in range(N):
        if len(q) == 0:
            impossible = True
            break
        elif len(q) > 1:
            ambiguous = True
            break

        cur = q.popleft()
        result.append(cur)

        for j in range(1, N + 1):
            if graph[cur][j]:
                indegree[j] -= 1

                if indegree[j] == 0:
                    q.append(j)

    if ambiguous:
        print("?")
    elif impossible:
        print("IMPOSSIBLE")
    else:
        print(' '.join(map(str, result)))

 

구현 난이도도 살짝 있어서 중간중간 정답지 슬쩍슬쩍 보면서 구현했다. 로직을 이해해도 자잘자잘한 실수를 많이 할 수 있는 문제였음.