[Python] BOJ / 2617번 / 구슬 찾기

2617번: 구슬 찾기

---

📝 풀이

• N개의 구슬에 대한 M개의 쌍의 대한 비교 결과를 통해 무게가 중간인 구슬이 될 수 없는 구슬의 개수를 구하는 프로그램
• DFS, BFS 등 여러가지 방법으로 구현할 수 있지만 필자의 경우 플로이드-와샬 알고리즘을 사용하였다.
• 알고리즘의 진행 과정은 다음과 같음
  • 구슬 쌍에 대한 비교 결과를 배열에 저장
  • 위 과정에서 나온 배열을 통해 플로이드-와샬 알고리즘 수행
  • 이후 완성된 배열에서 각 구슬에 대해 더 가벼운 구슬과 더 무거운 구슬의 개수를 구하여 중간이 될 수 있는지 없는지 검사
    • 어떤 구슬에 대해서 가벼운 구슬의 개수 또는 무거운 구슬의 개수가 n // 2 보다 크다면 중간이 될 수 없다는 뜻

---

💻 소스코드

import sys

input = sys.stdin.readline

def floyd():
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if dp[i][k] == 1 and dp[k][j] == 1:
                    dp[i][j] = 1

n, m = map(int, input().split())
dp = [[0] * (n + 1) for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, input().split())
    dp[a][b] = 1

floyd()

ans = 0
for i in range(1, n + 1):
    light_cnt = heavy_cnt = 0
    for j in range(1, n + 1):
        if i == j: continue
        elif dp[i][j] == 1:
            light_cnt += 1
        elif dp[j][i] == 1:
            heavy_cnt += 1
    if light_cnt > n // 2 or heavy_cnt > n // 2:
        ans += 1

print(ans)