새소식

반응형
Algotithms

[백준] 3665 최종 순위 🌟

  • -
728x90
반응형

문제

  • 1번 ~ N번까지의 N개의 팀 중 작년과 상대적 순위가 바뀐 팀 목록만 발표하려고 한다.
    • 작년에 팀13이 팀6보다 순위가 높았는데, 올해 팀6이 팀13보다 순위가 높다면, (6, 13)을 발표한다.
    • 2 <= N <= 500
  • 작년 순위와 상대적 순위가 바뀐 M개 팀의 목록이 주어졌을 때, 올해 순위를 만들어라.
    • 0 <= M <= 25000
  • 만약 확실한 순위를 찾을 수 없다면 ? 를 출력하고, 
  • 데이터 일관성이 없어 순위를 정할 수 없는 경우에는 "IMPOSSIBLE" 을 출력한다.

 

풀이

  • '순서' 라서 위상정렬을 떠올렸지만 어떻게 정렬할지 감을 못잡았다.
  • 자신보다 순위가 낮은 팀을 가리키도록 방향 그래프를 만든 후 위상정렬을 수행해 순위를 매길 수 있다.
  • 여기서, 사이클이 발생하면 IMPOSSIBLE 한 경우가 되고,
    • 일반적인 위상정렬의 경우 N개의 노드를 큐에서 출력하지만 N번이 나오기 전에 큐가 비면 사이클이 발생한 것으로 볼 수 있다.
  • 위상 정렬 결과가 1개가 아니라 여러 가지가 나오는 경우는 ? 을 출력해야할 경우가 된다.
    • 큐에서 노드 뽑은 후 큐의 원소가 1개가 아니면 위상 정렬의 결과가 여러 개라고 볼 수 있다.
  • => 위상 정렬 수행 과정에서 큐에서 노드를 뽑을 때 큐의 원소가 항상 1개로 유지되는 경우에만 고유 순위가 존재한다고 볼 수 있다.

 

from collections import deque for _ in range(int(input())): # 테스트 케이스 반복 N = int(input()) # 팀의 수 indegree = [0] * (N+1) # 진입 차수 graph = [[False]*(N+1) for _ in range(N+1)] # 방향 그래프 # 작년 순위 입력받기 data = list(map(int, input().split())) for i in range(N): for j in range(i+1, N): graph[data[i]][data[j]] = True # i -> j 낮은 팀 가리키기 indegree[data[j]] += 1 # 낮은 팀 진입차수 +1 M = int(input()) # 바뀐 순위 정보 개수 for _ in range(M): a, b = map(int, input().split()) # a가 b보다 낮았는데 높아졌다 # 간선 방향 뒤집기 # 현재 a가 b보다 높은 경우 if graph[a][b] : graph[a][b] = False graph[b][a] = True indegree[a] += 1 indegree[b] -= 1 # 현재 a가 b보다 낮은 경우 else: graph[a][b] = True graph[b][a] = False indegree[a] -= 1 indegree[b] += 1 # 위상 정렬 result = [] # 순위 리스트 q = deque() # 진입 차수 0인 노드 큐에 삽입 for i in range(1, N+1): if indegree[i] == 0: q.append(i) only_one = True # 경우의 수가 하나인 경우 cycle = False # 사이클이 존재하는 경우 for i in range(N): if len(q) == 0 : # N번 반복 전에 큐가 비었다! cycle = True # 사이클이 존재한다. break if len(q) >= 2: # 큐에 2개 이상의 노드가 있다! only_one = False # 여러 개 경우의 수가 존재한다. break # 현재 노드와 연결된 노드들 진입차수 -1 now = q.popleft() result.append(now) for j in range(1, N+1): if graph[now][j] : indegree[j] -= 1 if indegree[j] == 0: # 새로 진입차수 0이 되는 노드 삽입 q.append(j) if cycle: print("IMPOSSIBLE") elif not only_one: print("?") else: print(*result)

 

References

  • 이것이 코딩테스트다 Q 45
  • 백준 3665번
반응형
Contents

포스팅 주소를 복사했습니다

이 글이 도움이 되었다면 공감 부탁드립니다.