(BOJ3665 최종 순위

• tags : (algorithm

  No matching post could be found

  - (topological sort
• 문제 링크 : https://www.acmicpc.net/problem/3655
• 풀이 링크
  • Python

• 루트로부터 자식이 1개만 존재하는 트리에서, 특정 점들의 상대적 위치가 변경되었을 때, 똑같이 루트로부터 자식이 1개만 존재하는 트리가 될 수 있는지 확인하는 문제이다.
• 모든 점들의 상대적 위치를 저장하고, 순서가 변경된 경우, 따로 저장하여 확인한다.

N = II()
grades = list(MIIS())
M = II()
changed_grades = set(tuple(MIIS()) for _ in range(M))

teams = [[] for _ in range(N + 1)]
teams_before = [0] * (N + 1)
for i in range(N):
    for j in range(i + 1, N):
        a, b = grades[i], grades[j]
        if (a, b) in changed_grades or (b, a) in changed_grades:
            a, b = b, a
        teams[a].append(b)
        teams_before[b] += 1

• 입력을 먼저 처리한다.
• teams에는 더 낮은 순위의 팀들을 저장하고, teams_before에는 더 높은 순위의 팀의 수를 저장한다.
• 모든 팀 사이 상대 순위를 저장하기 위한 for문 순회를 하고, 만약 두 팀 쌍의 순위 순서가 변경되었다면, 순서를 변경시켜 적용한다.

queue = deque([])
for i in range(1, N + 1):
    if not teams_before[i]:
        queue.append((i))
if not queue:
    print("IMPOSSIBLE")
    continue
ans = []
while queue and len(ans) < N:
    if len(queue) >= 2:
        break
    x = queue.popleft()
    ans.append(x)
    for y in teams[x]:
        teams_before[y] -= 1
        if not teams_before[y]:
            queue.append(y)
        elif teams_before[y] < 0:
            break
    else:
        continue
    break
if len(ans) == N:
    print(*ans)
else:
    print("IMPOSSIBLE")

• 문제에서 원하는 ?가 나오는 결과는 존재하지 않을 것 같아 제외했다.
• 먼저 가장 높은 등수의 팀을 찾고, queue에 추가한다.
  • 이 문제는 항상 한 팀만 queue에 들어 있어야 하므로 stack을 쓰거나 하나의 변수만 활용해도 문제 없을 것으로 보인다.
  • 만약 queue에 여러 개의 값이 있다면 트리가 아니게 되어 순서를 판단할 수 없다.