[백준/Python] 2458번(DFS)_키 순서

📌문제 유형

그래프 이론, 그래프 탐색, DFS, 플로이드-워셜 (골드 Lv.4)

 

📌문제

2458번: 키 순서

 

📌나의 문제풀이

- 같은 번호 내, 해당 번호보다 키가 작으면 before, 해당 번호보다 키가 크면 after에 넣어서 DFS 실행

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

maps = [[[],[]] for _ in range(n+1)]	# before, after
for _ in range(m):
    a,b = map(int,input().split())
    maps[a][1].append(b)	# after
    maps[b][0].append(a)	# before

def dfs(i, j):
    for num in maps[i][j]:
        if visited[num] == 0:
            visited[num] = 1
            dfs(num,j)

ans = 0
for i in range(1,n+1):
    visited = [0 for _ in range(n+1)]
    visited[i] = 1
    for j in range(0,2):    # before, after
        dfs(i, j)
    if sum(visited) == n:
        ans += 1
print(ans)

 

📌 다른사람의 문제풀이

- 플로이드 워셜 활용

https://claude-u.tistory.com/339

#288 백준 파이썬 [2458] 키 순서 - 플로이드 와샬

import sys

#입력
N, M = map(int, input().split())
height = [[0 for _ in range(N+1)] for _ in range(N+1)]

for _ in range(M):
    tall, short = map(int, sys.stdin.readline().split())
    height[tall][short] = 1

#플로이드 와샬 알고리즘
for k in range(1, N+1): #경로 for문이 가장 상위 단계여야 누락되지 않는다(k는 학생)
    for i in range(1, N+1):
        for j in range(1, N+1):
            if height[i][j] == 1 or (height[i][k] ==1 and height[k][j] == 1):
                height[i][j] = 1 #자신보다 작은 경우


#출력
answer = 0
for i in range(1, N+1):
    known_height = 0
    for j in range(1, N+1):
        known_height += height[i][j] + height[j][i] #자신보다 작은사람과 큰사람의 합
    if known_height == N-1: #자신의 키 순서를 알 경우
        answer += 1
print(answer)

 

📌 리뷰

- 플로이드 워셜

• 모든 정점 사이의 최단 경로를 찾는 탐색 알고리즘
• 단방향 그래프일때 사용
• min(maps[i][j], maps[i][k] + maps[k][j])

플로이드-워셜(Floyd-Warshall) 알고리즘 이론과 파이썬 구현