[백준/Python] 2458번 - 키 순서

문제

백준 2458번 - 키 순서

해결 과정

1. height 배열

• j보다 i가 크다면 height[i][j] = 1

2. 플로이드 와샬

• height[i][k] == 1 and height[k][j] == 1
  i가 k보다 크고 k는 j보다 크다는 뜻
  그렇다면 i는 j 보다 크다는 것!
  ----> height[i][j] = 1

3. 기준값(i)보다 작은 키는 몇명이고 큰 키는 몇 명인지 확인하기

• answer: 자신의 키가 몇 번째인지 알 수 있는 학생의 수
• check: 기준보다 작은 키를 가진 학생의 수 + 기준보다 큰 키를 가진 학생의 수
• i와 j를 비교했다면 1이 되니까 비교 횟수가 몇인지 check에 더 해준다.
• check 가 n-1과 같다면 자신의 키가 몇 번째인지 알 수 있으므로
  answer에 1을 더해준다.

풀이

import sys
n, m = map(int,sys.stdin.readline().split())
height = [[0] * (n+1) for _ in range(n+1)]
        
for _ in range(m):
  short, tall = map(int,sys.stdin.readline().split())
  height[tall][short] = 1

# 플로이드 와샬
for k in range(1,n+1):
  for i in range(1, n+1):
    for j in range(1, n+1):
      if height[i][k] == 1 and height[k][j] == 1:
        height[i][j] = 1


answer = 0
for i in range(1,n+1):
  check = 0
  for j in range(1,n+1):
    check += (height[i][j] + height[j][i])
  if check == (n-1):
    answer += 1

print(answer)