[Baekjoon Online Judge] 백준 10159번 저울(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 10159번 저울

(Python)

(글쓴날 : 2020.06.13)

 

---

* Baekjoon Online Judge, 백준 10159번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 10159번 저울

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/10159

10159번: 저울

---

2) 풀이 과정

* 시간 복잡도 : O(EV²)

 

무게가 서로 다른 N개의 물건이 주어지고, 일부 물건 쌍에 대해 저울로 어떤 것이 무거운지 측정한 결과가 주어질 때, 각 물건에 대해 다른 물건과의 비교 결과를 알 수 없는 물건의 개수를 구하는 문제입니다.

 

저의 경우, 플로이드 와샬 알고리즘을 적용하였고, Python을 사용했습니다.

먼저, 주어지는 정보들을 인접 행렬로 구현한 뒤, 플로이드 와샬 알고리즘을 적용해 어떤 물건을 대신 이용하여 다른 물건에 대한 비교 결과를 구할 수 있는지 알아내어 문제를 해결했습니다.

예를 들어, [1] > [2], [2] > [3]일 경우 1번 정점에서 출발해 2번 정점을 거쳐 3번 정점으로 가는 경로가 있는지 확인하는 그래프 문제와 일치합니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
def floydWarshall():
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if adjMatrix[i][k] and adjMatrix[k][j]:
                    adjMatrix[i][j] = 1
 
N = int(input())
M = int(input())
 
adjMatrix = [[0] * N for _ in range(N)]
    
for _ in range(M):
    a,b = map(int,input().split())
 
    adjMatrix[a-1][b-1] = 1
 
floydWarshall()
 
for i in range(N):
    ans = 0
 
    for j in range(N):
        if i == j:
            continue
        
        if not adjMatrix[i][j] and not adjMatrix[j][i]:
            ans += 1
 
    print(ans)

---