백준 - 10159번 저울 python 문제풀이 [Hellfer]

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

10159번: 저울

🔷 알고리즘 분류 - 플로이드-워셜, 난이도 - 골드 4

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

플로이드 워셜이란?

플로이드 워셜(Floyd-Warshall) 알고리즘은 그래프에서 모든 노드 간의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 '모든 노드'를 '중간에 거치는 노드'로 삼아 '모든 노드 쌍'에 대한 최단 경로를 계산합니다.

본질적으로 플로이드 워셜 알고리즘은 다이내믹 프로그래밍 기법을 사용합니다. 그래프의 각 노드를 순회하면서 그 노드를 거쳐가는 모든 노드 쌍에 대한 최단 거리를 갱신해 나갑니다. 이렇게 하면 각 노드를 거쳐가는 모든 경우를 고려하게 되므로, 결과적으로 모든 노드 간의 최단 거리를 구할 수 있습니다.

플로이드 워셜 알고리즘이 사용되는 경우는 주로 '모든 노드 간의 최단 경로'를 한 번에 알아야 하는 경우입니다. 그리고 이 알고리즘의 시간 복잡도는 O(N^3)입니다 (N은 노드의 개수). 따라서, 노드의 개수가 500개 이하인 경우에 주로 사용되는 편입니다.

단, 플로이드 워셜 알고리즘은 음의 사이클을 감지할 수 없으므로, 그래프에 음의 사이클이 존재하는 경우에는 사용할 수 없습니다.

 

플로이드 워셜 알고리즘에서 사용되는 점화식은 다음과 같습니다.

D_ab = min(D_ab, D_ak + D_kb)

여기서 D_ab는 노드 a에서 노드 b로 가는 최단 거리를 의미하며, D_ak는 노드 a에서 노드 k로 가는 최단 거리, D_kb는 노드 k에서 노드 b로 가는 최단 거리를 의미합니다.

이 점화식은 "a에서 b로 바로 가는 거리"와 "a에서 k를 거쳐 b로 가는 거리" 중 어떤 것이 더 짧은 지를 판단하는 것을 의미합니다. 만약 a에서 k를 거쳐 b로 가는 거리가 더 짧다면, a에서 b로 가는 최단 거리를 그 값으로 갱신합니다.

이 점화식을 통해 모든 노드를 거쳐보면서 최단 거리를 갱신해 나가는 것이 플로이드 워셜 알고리즘의 핵심입니다. 이 알고리즘은 모든 노드를 한 번에 거쳐보며 최단 경로를 찾는 방식으로, 각 노드를 거쳐가는 모든 경우를 고려하여 최단 경로를 찾습니다.

 

n=int(input())  # 물건의 개수 N 입력 받기
m=int(input())  # 무게 비교 횟수 M 입력 받기

# 무게 비교 결과를 저장할 2차원 리스트 초기화
# graph[i][j] = 1이면 i번 물건이 j번 물건보다 무겁다는 뜻입니다.
graph=[[0] * (n) for _ in range(n)]

# 무게 비교 결과를 입력 받아서 2차원 리스트에 저장
for _ in range(m):
    x,y=map(int,input().split())
    graph[x-1][y-1]=1  # x번 물건이 y번 물건보다 무겁다는 정보 저장
    
# 플로이드-워셜 알고리즘을 통해 각 물건이 다른 물건보다 무겁거나 가벼운지 판단
for k in range(n):
    for i in range(n):
        for j in range(n):
            if graph[i][k] and graph[k][j]:  # i번 물건이 k번 물건보다 무겁고, k번 물건이 j번 물건보다 무거우면
                graph[i][j]=1  # i번 물건이 j번 물건보다 무겁다는 정보 저장
                
# 각 물건에 대해 무게를 비교할 수 없는 물건의 개수를 세어 출력
for i in range(n):
    cnt=0  # 무게를 비교할 수 없는 물건의 개수를 저장할 변수
    for j in range(n):
        if not graph[i][j] and not graph[j][i]:  # i번 물건과 j번 물건의 무게를 비교할 수 없으면
            cnt+=1  # 카운트 증가
    print(cnt-1)  # 자기 자신을 제외한 무게를 비교할 수 없는 물건의 개수 출력

 

🔶 초보자를 위한 생각주머니 키우기

🔸해결전략

1. 먼저 입력값으로 물건의 개수 N과 비교 횟수 M을 받습니다.

2. 그다음에는 비교 결과를 입력받아, 무거운 물건 a와 가벼운 물건 b가 주어지면, graph [a][b] = 1로 설정합니다. 이는 물건 a가 물건 b보다 무겁다는 것을 의미합니다.

3. 모든 비교 결과를 입력받은 후에는 플로이드-워셜 알고리즘을 수행합니다. 이 알고리즘은 모든 노드에 대해 다른 모든 노드로의 최단 경로를 찾는 알고리즘입니다. 여기서는 무게 비교 결과를 통해 각 물건이 다른 물건보다 무겁거나 가벼운지를 판단합니다.

4. 플로이드-워셜 알고리즘을 수행한 후에는 각 물건에 대해 무게를 비교할 수 없는 물건의 개수를 세어 출력합니다. 이를 위해 if not graph [i][j] and not graph [j][i] 조건을 확인합니다. 이는 물건 i가 물건 j보다 무겁거나 가벼운지를 판단할 수 없는 경우를 의미합니다.

예를 들어, 물건의 개수 N이 6개, 비교 횟수 M이 7번, 그리고 비교 결과가 다음과 같이 주어졌다고 가정해 봅시다.

 

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

 

플로이드-워셜 알고리즘을 수행한 후에는 각 물건이 다른 물건보다 무겁거나 가벼운지를 나타내는 2차원 배열 graph가 아래와 같이 갱신됩니다.

 

0 1 1 1 1 1
0 0 1 1 1 1
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1
0 0 0 0 0 0

 

마지막으로, 각 물건에 대해 무게를 비교할 수 없는 물건의 개수를 세어 출력합니다. 이 경우에는 물건 1, 2, 3은 무게를 비교할 수 없는 물건이 없으므로 0을 출력하고, 물건 4, 5, 6은 무게를 비교할 수 없는 물건이 2개 있으므로 2를 출력합니다. 따라서 최종 출력 결과는 다음과 같습니다.

 

0
0
0
2
2
2

 

🤗파이팅입니다~ 여러분!!🤗