[백준] 10159 저울

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

모든 물건들에 대해서 각 물건이 다른 물건들과 무게 비교가 가능한지 탐색하는 문제입니다.

모든 물건들에 대해서 탐색이 필요하므로, 플로이드 워셜을 이용하엿습니다.

 

물건들을 비교하였을 때 순서에 대한 정보는 필요가 없으므로, 해당 물건 보다 크거나 작은지에 대한 정보만 기록하였습니다.

2) 알고리즘

• 플로이드 워셜

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

N = int(sys.stdin.readline())               # 물건의 개수
M = int(sys.stdin.readline())               # 물건 비교한 횟수
order = [[0] * N for _ in range(N)]         # 물건들 간 무게 순서 정보

for _ in range(M):
    light, heavy = map(int, sys.stdin.readline().split())   # 가벼운 것, 무거운 것
    order[light-1][heavy-1] = 1                             # 가벼운 물건 뒤에 무거운 물건이 오므로 1 로 지정

for k in range(N):
    for i in range(N):
        for j in range(N):
            if order[i][k] and order[k][j]:     # i 보다 k 가 무겁고, k 보다 j 가 무거운 경우
                order[i][j] = 1                 # i 보다 j 가 무거우므로 1 지정

for i in range(N):                  # 해당 물건 번호의 행과 열에서 1 인 경우
    cnt = sum(order[i])             # 무게 비교가 되는 물건이므로
    for j in range(N):
        cnt += order[j][i]
    print(N-cnt-1)                  # N 개의 물건에서 1의 개수를 뺌 (1을 추가적으로 빼는건 자기 자신도 빼야하므로)

---

🔗 문제 링크

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

10159번: 저울

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다