[Python] 백준 10159 저울

1. 문제 링크

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

10159번: 저울

---

2. 문제 요약

• 비교 결과를 알 수 없는 물건의 개수 구하기

---

3. 아이디어 정리

1. 플로이드와샬을 이용해 모든 노드에서 다른 노드 경로 구하기
2. a > b 가는 경로가 없는 경우(비교 결과를 알 수 없는 경우), count + 1 해주기

플로이드와샬 개념

모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. - 특정 노드를 거쳐 가는 경우 사용

• 2차원 테이블에서 최단 거리 정보를 저장한다.
• 특정 노드를 거쳐 가는 경우 사용하면 좋다.

플로이드 워셜 점화식

각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다.

• a에서 b로 가는 최단 거리, a에서 k를 거쳐 b로 가는 거리 비교

 

---

4. 문제 풀이

4-1. 내 풀이

import sys

INF = int(1e9)
n = int(sys.stdin.readline())  # 물건의 개수
m = int(sys.stdin.readline())  # 측정된 물건의 쌍
# 2차원 그래프, 모든 값을 무한으로 초기화

graph = [[INF] * (n + 1) for _ in range(n + 1)]   # 거리를 담는 테이블

# 1. 자기 자신으로 가는 노드 비용을 0으로 초기화
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 1

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

# 2. 플로이드와셜 점화식 - a에서 b로 가는 경로가 있는지 확인 
for k in range(1, n + 1):
    for a in range(1, n + 1):   # 출발 노드
        for b in range(1, n + 1):   # 도착 노드
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 3. a, b 비교 가능한지 확인 
for a in range(1, n + 1):
    count = 0
    for b in range(1, n + 1):
        if graph[a][b] == INF and graph[b][a] == INF:  # a>b, b>a 가는 경로가 없는 경우 + 1
            count += 1
    print(count)

 

---

5. 결론

• 플로이드와샬을 이용하면 쉬운 문제 but 플로이드와샬을 사용해야 하는지 알기 어려웠다!