[코테 스터디] 그래프 이론, 최종 순위

Q45. 최종 순위

🐣문제

올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다.

올해는 인터넷 예선 본부에서는 최종 순위를 발표하지 않기로 했다. 그 대신에 작년에 비해서 상대적인 순위가 바뀐 팀의 목록만 발표하려고 한다. (작년에는 순위를 발표했다) 예를 들어, 작년에 팀 13이 팀 6 보다 순위가 높았는데, 올해 팀 6이 팀 13보다 순위가 높다면, (6, 13)을 발표할 것이다.

창영이는 이 정보만을 가지고 올해 최종 순위를 만들어보려고 한다. 작년 순위와 상대적인 순위가 바뀐 모든 팀의 목록이 주어졌을 때, 올해 순위를 만드는 프로그램을 작성하시오. 하지만, 본부에서 발표한 정보를 가지고 확실한 올해 순위를 만들 수 없는 경우가 있을 수도 있고, 일관성이 없는 잘못된 정보일 수도 있다. 이 두 경우도 모두 찾아내야 한다.


백준 링크 | https://www.acmicpc.net/problem/3665

🐥풀이

순위 관련..!! 위상정렬 알고리즘 활용이 필요한 문제이다. 😲 개인적으로 그래프 이론 중 젤 어렵고 이해가 힘들었던 알고리즘이었다. 😫


위상정렬 알고리즘
순서가 정해져있는 작업을 순서대로 처리하는 알고리즘이다.

대표적인 예시로 대학의 선수과목, 후수과목이 있다. B과목을 듣기 위해서 A과목을 들어야 한다면, (A->B) A는 선수과목, B는 A의 후수과목이 되겠다. 그럼 위상정렬은 A B 순서로 작업을 처리한다.

코드로 구현할 때, 간선정보 리스트와 진입차수를 활용하게 된다. A가 선수과목이고 B가 후수과목이면,

간선정보
graph[A] = {B}가 된다. (물론 과목 C도 A의 후수과목이면 graph[A].append(C)하여 graph[A] = {B, C}가 되겠다.)

진입차수
진입차수는 특정 노드가 처리되기 위해 먼저 처리되어야 할 노드의 수라고 생각하면 되겠다. 예를 들어 B과목을 듣기 위해 A과목을 먼저 들어야 한다면, B과목의 진입차수는 1이다. A과목을 듣는데 먼저 들어야 할 과목의 제약이 없다면, A과목의 진입차수는 0이다. 또한, C과목을 듣기 위해서 A과목을 들은 후 B과목을 들은 후에야 C과목을 들을 수 있다면, C과목 노드의 진입차수는 2가 되겠다.


위상정렬을 간략하게나마 정리해보았다. 그럼 이제 위상정렬을 이 문제에서 어떻게 활용할 수 있을까..?

일단 전체 팀의 순위를 추측하는 문제이므로 위상정렬을 사용해야겠다.
그리고 입력값으로 작년 팀의 순위가 주어진다. 그럼 이 순위를 간선정보와 진입차수 리스트에 정리해보자.

  # 간선, 진입차수 초기화

  graph, indegree = [[] for _ in range(n+1)], [0]*(n+1)

  for i in range(n-1):
    for j in range(i+1,n):
      graph[ranking[i]].append(ranking[j])
      indegree[ranking[j]] += 1

(graph가 간선정보, indegree가 진입차수 정보를 담는 리스트이다. ranking은 입력값으로 받은 작년 순위 정보이다.) 이중반복문을 돌렸다. 입력값은 순위의 오름차순으로 팀의 숫자가 주어졌으므로, i번 팀이 j번 팀보다 순위가 높다.

순위가 높을수록 간선 정보가 늘어나고, 순위가 낮을수록 진입차수가 늘어난다.
따라서 graph[i번 팀].append([j번 팀])으로 간선 정보를, indegree[j번팀]+=1으로 진입차수를 초기화 할 수 있다.


작년 순위를 토대로 간선 및 진입차수 리스트를 초기화 했다. 그럼 다음으로는 순위 변동이 일어난 정보들이 입력값으로 들어온다. 순위 변동된 팀끼리 서로 reverse 해주자.

    # 순위 변동 (간선 업데이트 : reverse)

    # 작년 기준 a팀이 b팀보다 순위 높았음
    if b in graph[a]:
      graph[a].remove(b)
      indegree[b] -= 1
      graph[b].append(a)
      indegree[a] += 1
    # 작년 기준 b팀이 a팀보다 순위 높았음
    else:
      graph[b].remove(a)
      indegree[a] -= 1
      graph[a].append(b)
      indegree[b] += 1

간단하다. 간선정보와 진입차수를 순위변동한 팀끼리 바꿔주면 된다 ㅎㅁㅎ


이제 올해의 순위 정보를 토대로 간선 정보와 진입차수 리스트도 모두 업데이트 되었다. 이제 순위가 높은 팀부터 차례대로 처리해보자.

  while queue:
    team = queue.pop(0)
    result.append(team)

    for t in graph[team]:
      indegree[t] -= 1 # 진입차수 빼기

      # 진입차수 없으면(0, queue에 담긴 팀들 제외하고 해당 팀보다 더 높은 팀 없음)
      if indegree[t]==0:
        queue.append(t)
      elif indegree[t]<0: # 예외처리. 진입차수가 0 미만일 수 없음
        flag = False
        break

queue에 진입차수가 0인 노드를 미리 담아두었다. 진입차수가 0인 것은 곧 앞에 어떤 노드도 없는, 1위임을 의미한다. 냅다 결과 리스트에 넣어주자 ㅎㅎ
그리고 해당 노드(팀)와 간선으로 연결된 노드들을 반복문을 통해 처리해준다. 선수 노드가 하나 빠졌으므로 진입차수를 하나씩 빼주고, 만약 진입차수가 0인 노드가 생기면, 냅다 queue에 넣어준다. (앞에 더 올 노드가 없다는 뜻이므로) 이 과정을 반복한 후의 결과 리스트는 순위대로 팀의 번호가 담겨있을 것이다. (오예!)


하지만 정확한 순위를 알 수 없는 경우도 있을 수 있다고 했다.

1. 진입차수가 0인 노드(팀)이 없는 경우.
1위가 없다..? 정확한 순위를 내지 못했다는 뜻이 되므로 정확한 순위를 알 수 없는 경우가 된다.

2. 진입차수가 0인 노드(팀)이 여러 개인 경우.
1위가 여러 팀..? 1위 후보가 여러 팀..? 정확한 순위를 내지 못했다는 뜻이 된다.


위와 같은 과정을 반복하며 입력값으로 들어오는 모든 경우의 결과를 출력해주면 되겠다.

🐓코드

for _ in range(int(input())):
  # 팀 수, 순위정보
  n, ranking = int(input()), list(map(int, input().split()))

  # 간선, 진입차수 초기화
  graph, indegree = [[] for _ in range(n+1)], [0]*(n+1)
  for i in range(n-1):
    for j in range(i+1,n):
      graph[ranking[i]].append(ranking[j])
      indegree[ranking[j]] += 1


  for _ in range(int(input())):
    a, b = map(int, input().split())  # a -> b

    # 순위 변동 (간선 업데이트 : reverse)
    if b in graph[a]:
      graph[a].remove(b)
      indegree[b] -= 1
      graph[b].append(a)
      indegree[a] += 1
    else:
      graph[b].remove(a)
      indegree[a] -= 1
      graph[a].append(b)
      indegree[b] += 1

  queue, flag, result = [], True, []
  
  # 진입차수가 0인 팀번호
  for i in range(1,n+1):
    if indegree[i]==0:
      queue.append(i)

  # 하나는 진입차수 0이어야 함. 아니면 싸이클
  if not queue:
    print("IMPOSSIBLE")
    continue

  while queue:
    # 동시에 두 노드가 진입차수 0이면 싸이클 발생
    if len(queue)>1:
      flag = False
      break

    team = queue.pop(0)
    result.append(team)
    
    for t in graph[team]:
      # 진입차수 빼기
      indegree[t] -= 1

      # 진입차수 없으면(0, queue에 담긴 팀들 제외하고 해당 팀보다 더 높은 팀 없음)
      if indegree[t]==0:
        queue.append(t)
      elif indegree[t]<0: # 예외처리. 진입차수가 0 미만일 수 없음
        flag = False
        break

        
  # 정확한 순위 알 수 없음
  if not flag or len(result)<n:
    print("IMPOSSIBLE")
  # 정확한 순위 출력
  else:
    print(" ".join(map(str, result)))

⭐2022.05.12

우왁 실전 마지막 문제는 정말 무지막지 어려웠다 ㅠㅠ 사실 위상정렬 문제는 거의 못 풀었었고 이해도 못하고 넘어간 부분이 많았었는데 스터디와 이번 회고로 좀 더 잘 이해할 수 있게 된 것 같아서 뿌듯하다 ㅎㅎ

회고를 마치며..

목표로 두었던 코테 스터디에서 코드 리뷰했던 실전 문제들의 회고 포스트가 끝났다 ㅇㅁㅇ..!! 살면서 장기 목표는 중간에 포기한 일도 많았었는데 스터디부터 회고까지 생각한 목표를 달성할 수 있어서 너무 뿌듯하다🥰

또한, 분명 직접 풀었으니 다시 보면 알겠지~ 라고 은연 중에 생각도 했었는데 회고를 통해 아직 공부를 많이 해야겠음을 깨달았다 ㅎㅎ.. 보자마자 풀이방법이 기억나지는 않지만 과거의 내가 푼 기록들을 보면 다시 기억이 새록새록 났던 문제가 유독 많았다..!

그래도 이번 회고를 통해 유명한 알고리즘을 한번씩 훑어보면서 다시 복습해볼 수 있었다. 회고 시작한 과거의 나 칭찬해 ㅎㅎ 미래의 내가 해냈어 >.<!!

그래도 아직 멀었음을 깨닫고.. 공부하자!!!!




목표한 코테 스터디 실전문제 회고 끝~! (짝짝)