문제풀이/BOJ
[Python] BOJ/백준 10159번 저울
서채리
2022. 8. 26. 00:43
[문제]
https://www.acmicpc.net/problem/10159
10159번: 저울
첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩
www.acmicpc.net
[풀이]
2022.08.25 - [문제풀이/BOJ] - [Python] BOJ/백준 2458번 키 순서
[Python] BOJ/백준 2458번 키 순서
[문제] https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르
chaewsscode.tistory.com
이 문제와 아주아주~ 유사한 문제
이번 문제는 기준이 되는 정점이 다른 정점과 연결되지 않은 수를 구해야 한다.
[코드]
import sys
INF = int(1e9)
N = int(sys.stdin.readline())
things = [[0] * N for _ in range(N)]
for _ in range(int(sys.stdin.readline())):
thing1, thing2 = map(int, sys.stdin.readline().split())
things[thing1-1][thing2-1] = 1
for k in range(N):
for i in range(N):
for j in range(N):
if things[i][k] == 1 and things[k][j] == 1:
things[i][j] = 1
answer = 0
for i in range(N):
count = 0
for j in range(N):
count += things[i][j] + things[j][i]
print((N - 1) - count)