Chap 17. 최단경로 - Q38. 정확한 순위

  • 0
  • 0
0
0

1. 정확한 순위

  • 난이도
  • 풀이 시간
    • 40분
  • 시간 제한
    • 1초
  • 메모리 제한
    • 128MB

A. 📜 문제

선생님은 시험을 본 학생 N명의 성적을 분실하고, 성적을 비교한 결과의 일부만 가지고 있다. 학생 N명의 성적은 모두 다른데, 다음은 6명의 학생에 대하여 6번만 성적을 비교한 결과이다.

  • 1번 학생의 성적 < 5번 학생의 성적
  • 3번 학생의 성적 < 4번 학생의 성적
  • 4번 학생의 성적 < 2번 학생의 성적
  • 4번 학생의 성적 < 6번 학생의 성적
  • 5번 학생의 성적 < 2번 학생의 성적
  • 5번 학생의 성적 < 4번 학생의 성적

A번 학생의 성적이 B번 학생보다 낮다면 화살표가 A에서 B를 가리키도록 한다.

학생들의 성적을 비교한 결과가 주어질 때, 성적 순위를 정확히 알 수 있는 학생은 모두 몇명인지 계산하는 프로그램을 작성하라.

a. 예를 들면.

순위를 정확히 알 수 있는 학생이 있다. 예를 들어 1번 학생은 5번 학생보다 성적이 낮고, 5번 학생은 4번 학생보다 성적이 낮으므로 1번 학생은 4번 학생보다 성적이 낮다. 따라서 1번, 3번, 5번 학생은 모두 4번 학생보다 성적이 낮다고 볼 수 있다. 4번 학생은 2번 학생과 6번 학생보다 성적이 낮다. 즉, 4번 학생보다 성적이 낮은 학생은 3명이고, 성적이 높은 학생은 2명이므로 4번 학생의 성적 순위를 정확히 알 수 있다.

b. 입력 조건
  • 첫째 줄에 학생들의 수 N (2 <= N <= 500)과 두 학생의 성적을 비교한 횟수 M(2 <= M <= 10,000)이 주어진다.
  • 다음 M개의 각 줄에는 두 학생의 성적을 비교한 결과를 나타내는 두 양의 정수 A와 B가 주어진다. 이는 A번 학생의 성적이 B번 학생보다 낮다는 것을 의미한다.
c. 출력 조건
  • 첫째 줄에 성적 순위를 정확히 알 수 있는 학생이 몇 명인지 출력한다.
d. 테스트 케이스
  • 입력 예시

    
    6 6
    1 5
    3 4
    4 2
    4 6
    5 2
    5 4
    
    
  • 출력 예시

    
    1
    
    

B. 💡 내 답안

a. 😊 1, 2차 시도 (성공)

"""
Date    : 2021.11.24
Update  : 2021.11.24
Source  : Q38_정확한 순위.py
Purpose : 플로이드 알고리즘을 사용하여 학생들의 성적 순위를 알 수 있는 경우를 구함
Author  : 김학진 (mildsalmon)
Email   : mildsalmon@gamil.com
"""
# n = 학생들의 수
# m = 성적을 비교한 횟수
n, m = list(map(int, input().split()))
# 학생들의 성적 비교가 가능한 경우의 인접행렬
array = [[1e9]*(n+1) for i in range(n+1)]

# 초기 비교 횟수 입력
for i in range(m):
    A, B = list(map(int, input().split()))

    array[A][B] = 1

# 자기 자신과 비교하는 경우는 0으로 입력
for i in range(n+1):
    array[i][i] = 0

# i -> k -> j가 i -> j보다 작다면 값을 교체
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            array[i][j] = min(array[i][k] + array[k][j], array[i][j])

# print(*array, sep='\n')

result = 0

# A -> B인 경우와 B -> A인 경우 중 최단 거리를 구했다면, count를 증가시킴.
# count가 학생수와 같다면 결과값을 증가시킴.
for i in range(1, n+1):
    count = 0
    for j in range(1, n+1):
        if array[i][j] != 1e9 or array[j][i] != 1e9:
            count += 1
    if count == n:
        result += 1
print(result)

############
#### 플로이드로 안풀려서 다익스트라로 풀려고 했는데, cost 처리를 못함.
############

# from collections import deque
#
# n, m = list(map(int, input().split()))
#
# array = [[] for i in range(n+1)]
#
# distance = [0] * (n+1)
# q = deque()
#
# for i in range(m):
#     A, B = list(map(int, input().split()))
#
#     array[A].append(B)
#
# for i in range(n):
#     q.append(i)
#
# while q:
#     x = q.popleft()
#
#     for i in range(array[x]):
#         distance[x] += 1
#         distance[i] += distance[x]


b. 🙄 회고

내 풀이

  • 처음에는 플로이드로 접근했다가, 역방향(나보다 성적이 높은 학생)을 확인할 아이디어가 떠오르지 않았다.
    • 그래서 다익스트라로 풀려고 했다.
  • 그러나, 다익스트라로는 비용 처리를 할 방법이 떠오르지 않아서 실패했다.

결론

  • 단순히 역방향과 순방향을 모두 생각해야한다면, A -> B와 더불어 B -> A를 체크하는 방법을 고려했으면 쉽게 해결했을텐데..

C. 🧐 문제 해설

이해한 내용을 바탕으로 작성했습니다.

아래와 같은 방식으로 성적을 비교할 수 있다.

플로이드 워셜 알고리즘은 최단경로를 구해서 인접 행렬을 갱신한다. 이 말은 인접 행렬에서 1e9(무한대)가 아닌 것들은 A -> k -> B 혹은 A -> B로 구할 수 있다는 의미이다. 즉, A학생과 B학생 사이의 순서를 알 수 있다는 의미이다.

4번 학생을 기준으로 보면, 순방향(4번 학생보다 성적이 높은 학생)은 아래와 같이 표현할 수 있다.

그리고 역방향(4번 학생보다 성적이 낮은 학생)은 아래와 같이 표현할 수 있다.

우리는 4번 학생보다 성적이 높거나 낮은 학생들을 모두 아는 경우를 구해야한다. 그래야지 4번 학생의 정확한 순서를 유추할 수 있기 때문이다.

따라서, 기존의 플로이드 워셜 방식대로 알고리즘을 구현하고 순방향과 역방향을 모두 체크하면 된다.

a. 책 답안

python-for-coding-test/2.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

[1] 나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.