백준 - 2458번 키 순서 문제풀이 [Hellfer]

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

2458번: 키 순서

🔷 알고리즘 분류 - 깊이 우선 탐색, 플로이드 - 워셜

난이도 - 실버 1

플로이드-워셜 알고리즘은 그래프에서 모든 노드 간의 최단 거리를 찾는 알고리즘입니다. 

 

이 알고리즘은 가중치가 있는 방향 그래프와 가중치가 있는 무방향 그래프에서 모두 사용할 수 있습니다. 

 

또한 음의 가중치를 갖는 간선이 있어도 적용할 수 있지만, 음의 사이클이 있으면 안 됩니다.

플로이드-워셜 알고리즘은 다이내믹 프로그래밍 기법을 이용합니다. 

 

이 알고리즘은 그래프의 각 노드를 한 번에 하나씩 거쳐 가는 경우를 고려하여 최단 거리를 계산합니다. 

 

이때, 한 노드를 거쳐 가는 모든 경우를 고려하므로 모든 노드 간의 최단 거리를 찾을 수 있습니다.

플로이드-워셜 알고리즘의 시간 복잡도는 O(N^3)으로, 노드의 개수가 N일 때 N^3의 연산이 필요합니다. 

 

따라서 노드의 개수가 많지 않은 그래프에서 이 알고리즘을 사용하는 것이 적절합니다.

플로이드-워셜 알고리즘은 다음과 같은 순서로 진행합니다:

1. 먼저 모든 노드의 거리를 '무한대'로 초기화하고, 자기 자신으로의 거리는 0으로 설정합니다.

2. 그래프의 간선 정보를 이용하여 노드 간의 거리를 갱신합니다.

3. 모든 노드를 한 번에 하나씩 거쳐 가는 경우를 고려하여 최단 거리를 갱신합니다.

 

이때, i에서 j로 가는 거리가 i에서 k를 거쳐 j로 가는 거리보다 크다면 i에서 j로 가는 거리를 i에서 k를 거쳐 j로 가는 거리로 갱신합니다.

 

이 과정을 모든 노드에 대해 반복합니다.

🔶문제 풀이 - 플로이드 워셜을 이용한 풀이

import sys
input = sys.stdin.readline

# 학생 수(n)와 비교 정보의 수(m)를 입력받습니다.
n, m = map(int, input().split())
INF = int(1e9)  # 무한을 의미하는 값으로 10억을 설정

# 2차원 리스트(그래프)를 만들고, 모든 값을 무한으로 초기화합니다.
graph = [[INF] * (n+1) for _ in range(n+1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화합니다.
for a in range(1, n+1):
    for b in range(1, n+1):
        if a == b:
            graph[a][b] = 0

# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화합니다.
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로 가는 최소 비용을 찾아 갱신합니다.
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

result = 0
# 각 학생을 번호에 따라 한 명씩 확인하며 도달 가능한지 체크합니다.
for i in range(1, n+1):
    count = 0
    for j in range(1, n+1):
        # i에서 j로 가는 경로가 있거나, j에서 i로 가는 경로가 있다면
        # i와 j는 서로를 비교할 수 있다는 의미입니다.
        if graph[i][j] != INF or graph[j][i] != INF:
            count += 1
    # 해당 학생이 모든 다른 학생과 키를 비교할 수 있다면 결과값을 증가시킵니다.
    if count == n:
        result += 1
# 결과를 출력합니다.
print(result)

🔶문제 이해하기

다음과 같은 입력값이 주어졌다고 가정해 보겠습니다.

 

6 6
1 5
3 4
5 4
4 2
4 6
5 2

 

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

1번은 5번보다 키가 작고, 5번은 4번보다 작기 때문에, 1번은 4번보다 작게 됩니다.

 

그러면 1번, 3번, 5번은 모두 4번보다 작게 됩니다.

 

또한 4번은 2번과 6번보다 작기 때문에, 4번 학생은 자기보다 작은 학생이 3명이 있고, 자기보다 큰 학생이 2명이 있게 되어 자신의 키가 몇 번째인지 정확히 알 수 있습니다.

 

그러나 4번을 제외한 학생들은 자신의 키가 몇 번째인지 알 수 없습니다.

 

따라서 출력 결과는 1이 됩니다.

 

1