[Graph] 최종 순위
카테고리: Algorithm
최종 순위
난이도 : 🌕🌕🌕
푼횟수 : 🟡⚪⚪
올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다.
올해는 인터넷 예선 본부에서는 최종 순위를 발표하지 않기로 했다. 그 대신에 작년에 비해서 상대적인 순위가 바뀐 팀의 목록만 발표하려고 한다. (작년에는 순위를 발표했다) 예를 들어, 작년에 팀 13이 팀 6 보다 순위가 높았는데, 올해 팀 6이 팀 13보다 순위가 높다면, (6, 13)을 발표할 것이다.
창영이는 이 정보만을 가지고 올해 최종 순위를 만들어보려고 한다. 작년 순위와 상대적인 순위가 바뀐 모든 팀의 목록이 주어졌을 때, 올해 순위를 만드는 프로그램을 작성하시오. 하지만, 본부에서 발표한 정보를 가지고 확실한 올해 순위를 만들 수 없는 경우가 있을 수도 있고, 일관성이 없는 잘못된 정보일 수도 있다. 이 두 경우도 모두 찾아내야 한다.
입력 조건
첫째 줄에는 테스트 케이스의 개수가 주어진다. 테스트 케이스는 100개를 넘지 않는다. 각 테스트 케이스는 다음과 같이 이루어져 있다.
- 팀의 수 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
나의 풀이
문제 해설
문제에서 작년 순위와 상대적으로 순위가 바뀐 팀들의 목록이 주어졌을 때, ‘올해 순위’를 만들 것을 요구하고 있다. 즉 정해진 우선순위에 맞게 전체 팀들의 순서를 나열해야 한다.는 점에서 위상 정렬 알고리즘을 떠올릴 수 있어야 한다.
다시 말해 이 문제는 팀 간의 순위 정보를 그래프 정보로 표현한 뒤에, 위상 정렬 알고리즘을 이용해 해결할 수 있다. 문제에 제시된 예시 중 하나를 가지고 생각해보자.
위와 같은 작년의 순위 정보가 주어지면, ‘자기보다 낮은 등수를 가진 팀을 가리키도록’ 방향 그래프를 만들 수 있다. 이를 그래프로 표현하면 아래와 같다.
만약에 이대로 위상 정렬을 수행하게 되면, 수행 결과는 5 - 4 - 3 - 2 - 1이 된다. 즉, 문제에서 제시한 순위 정보와 동일하게 나온다. 다른 경우는 존재하지 않는다.
이제 상대적인 순위가 바뀌게 되는 경우에는, 해당 간선의 방향을 반대로 변경하면 된다. 예를 들어 팀 2와 팀 4가 순위가 바뀌고, 팀 3과 팀 4가 서로 순위가 바뀌면 아래와 같이 변경된다.
이후에 이 상태에서 위상 정렬을 다시 수행하면 된다. 위상 정렬은 2가지 특이 케이스가 존재한다.
1. 사이클이 발생하는 경우, 2. 위상 정렬의 결과가 1개가 아니라 여러 가지인 경우이다. 이 2가지 경우에 해당하지 않는다면 위상 정렬을 수행한 결과는 ‘오직 하나의 경우’만 존재하게 된다. 즉, 가능한 순위가 하나라는 의미가 된다.
따라서 변경된 상대적인 순위를 적용한 이후에, 위상 정렬 알고리즘을 실행하면서 사이클이 발생하는지, 혹은 결과가 여러 가지인지 확인하면 된다. 일반적인 위상 정렬의 경우, 정확히 N개의 노드가 큐에서 출력이 된다. 만약 노드가 N번 나오기 전에 큐가 비게 된다면, 사이클이 발생한 것으로 이해할 수 있다. 또한 특정 시점에 2개 이상의 노드가 큐에 한꺼번에 들어갈 때는, 가능한 정렬 결과가 여러 가지라는 의미가 된다. 그러므로 위상 정렬 수행 과정에서 큐에서 노드를 뽑을 때 큐의 원소가 항상 1개로 유지되는 경우에만 고유한 순위가 존재하는 것으로 이해할 수 있다.
그러므로 위상 정렬 소스코드에서 매 시점마다 큐의 원소가 0개이거나, 2개 이상인지를 체크하는 부분을 넣어주어 정답 소스코드를 작성할 수 있다.
문제 답안
from collections import deque
# 테스트 케이스만큼 반복
for tc in range(int(input())):
# 노드의 개수 입력 받기
n = int(input())
# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (n + 1)
# 각 노드에 연결된 간선 정보를 담기 위한 인접 행렬 초기화
graph = [[False] * (n + 1) for i 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
indegree[data[j]] += 1
# 올해 변경된 순위 정보 입력
m = int(input())
for i in range(m):
a, b = map(int, input().split())
# 간선의 방향 뒤집기
if graph[a][b]:
graph[a][b] = False
graph[b][a] = True
indegree[a] += 1
indegree[b] -= 1
else:
graph[a][b] = True
graph[b][a] = False
indegree[a] -= 1
indegree[b] += 1
# 위상 정렬(Topology Sort) 시작
result = [] # 알고리즘 수행 결과를 담을 리스트
q = deque() # 큐 기능을 위한 deque 라이브러리 사용
# 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
for i in range(1, n + 1):
if indegree[i] == 0:
q.append(i)
certain = True # 위상 정렬 결과가 오직 하나인지의 여부
cycle = False # 그래프 내 사이클이 존재하는지 여부
# 정확한 노드의 개수만큼 반복
for i in range(n):
# 큐가 비어있다면 사이클이 발생했다는 의미
if len(q) == 0:
cycle = True
break
# 큐의 원소가 2개 이상이라면 가능한 정렬 결과가 여러 개라는 의미
if len(q) >= 2:
certain = False
break
# 큐에서 원소 꺼내기
now = q.popleft()
result.append(now)
# 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
for j in range(1, n + 1):
if graph[now][j]:
indegree[j] -= 1
# 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
if indegree[j] == 0:
q.append(j)
# 사이클이 발생하는 경우(일관성이 없는 경우)
if cycle:
print("IMPOSSIBLE")
# 위상 정렬 결과가 여러 개인 경우
elif not certain:
print("?")
# 위상 정렬을 수행한 결과 출력
else:
for i in result:
print(i, end = ' ')
print()
기출 : NWERC 2010
링크 : https://www.acmicpc.net/problem/3665
🐢 현재 공부하고 있는 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저자 의 책을 학습하며 기록 및 정리를 하기위한 내용들입니다. 🐢
감사합니다.😊
댓글남기기