상세 컨텐츠

본문 제목

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

Problem Solving/Baekjoon Online Judge

by HelloMinchan 2020. 6. 13. 16:35

본문

© 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번: 저울

첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩

www.acmicpc.net


2) 풀이 과정

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

 

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

 

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

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

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


3) 코드

 

* Python 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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
 
= int(input())
= 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)

 

관련글 더보기

댓글 영역