[골드4] 2458번 : 키 순서

🛠 문제

https://www.acmicpc.net/problem/2458

👩🏻‍💻 해결 방법

플로이드 워셜 알고리즘(모든 지점에서 다른 모든 지점으로 가는 최단경로)을 사용하여 풀 수 있는 문제다
최단경로를 전부 갱신해준 뒤, 자신보다 키가 크거나 작은 사람의 수가 n-1(자신 제외한 수)이면 자신의 키가 몇 번째인지 알 수 있는 학생이다

소스코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [[0] * (n+1) for _ in range(n+1)]

for _ in range(m):
  a, b = map(int, input().split())
  graph[a][b] = 1

for k in range(1, n+1):
  for a in range(1, n+1):
    for b in range(1, n+1):
      # a가 b보다 작을 경우
      if graph[a][k] == 1 and graph[k][b] == 1:
        graph[a][b] = 1

answer = 0
for i in range(1, n+1):
  cnt = 0
  for j in range(1, n+1):
    # 자신보다 키가 큰 사람과 작은 사람 수의 합
    cnt += graph[i][j] + graph[j][i]
  # 자신과 비교해서 키를 알고 있는 사람이 자신 제외한 수만큼(n-1) 있을 경우
  if cnt == n-1:
    answer += 1

print(answer)

💡 다른 사람의 풀이

플로이드 워셜 알고리즘을 사용하면 python3으로 제출했을 경우 시간초과가 났기 때문에 다른 방법인 dfs를 사용한 풀이방법이다

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

graph = [[] for _ in range(n)]

for _ in range(m):
  a, b = map(int, input().split())
  if b-1 not in graph[a-1]:
    graph[a-1].append(b-1)

def dfs(i, idx, graph):
  for j in graph[idx]:
    if not check[i][j]:
      check[i][j] = 1
      check[j][i] = 1
      dfs(i, j, graph)

check = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n):
  check[i][i] = 1
  dfs(i, i, graph)

answer = 0
for row in check:
  if row == [1] * n:
    answer += 1

print(answer)