BOJ - 2617

백준 문제 링크
구슬 찾기

❓접근법

1. 플로이드 워셜 알고리즘을 활용했다.
2. 기본 플로이드 워셜 소스코드를 전개한다.
   자기 자신에게 가는 비용은 0
   graph[앞 번호 구슬][뒷 번호 구슬] = 1로 지정하고
   3중 반복문으로 graph를 갱신한다.
3. 찾고자 하는 것은 다음과 같다.

• 현재 구슬보다 작은 구슬이 N // 2개보다 많은가?
• 현재 구슬보다 큰 구슬이 N // 2개보다 많은가?

4. 따라서 다음 코드로 현재 구슬보다 작고, 큰 구슬의 개수를 구한다.

answer = 0
for i in range(1, n + 1):
    left_cnt = 0
    right_cnt = 0
    for j in range(1, n + 1):
        if i == j:
            continue
        elif graph[i][j] != INF: # 현재 구슬보다 크기가 작으면
            left_cnt += 1
        elif graph[j][i] != INF: # 현재 구슬보다 크기가 크면
            right_cnt += 1
    if left_cnt > n // 2 or right_cnt > n // 2:
    # 현재 구슬보다 작은 구슬이 n // 2개보다 많거나
    # 현재 구슬보다 큰 구슬이 n // 2개보다 많으면
        answer += 1

5. 마지막으로 answer를 출력하면 끝!

👌🏻코드

INF = int(1e9)

n, m = map(int, input().split())

graph = [[INF] * (n + 1) for _ in range(n + 1)]

for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0
            
for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = 1
    
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
            
answer = 0

for i in range(1, n + 1):
    left_cnt = 0
    right_cnt = 0
    
    for j in range(1, n + 1):
        if i == j:
            continue
            
        elif graph[i][j] != INF: # 현재 구슬보다 크기가 작으면
            left_cnt += 1
                
        elif graph[j][i] != INF: # 현재 구슬보다 크기가 크면
            right_cnt += 1
                
    if left_cnt > n // 2 or right_cnt > n // 2:
        answer += 1
        
print(answer)