[백준] 2617번 구슬 찾기

💡문제접근

• A → B의 관계를 A가 B보다 무겁다로 표현할 수 있다고 가정하자.
• graph[a][b]의 값이 True인 경우 a가 b보다 무겁다고 할 수 있다.

💡테스트케이스

입력
5 4
2 1
4 3
5 1
4 2

출력
2

• (5, 4), (2, 1), (5, 1)로 추론하면 5번은 4번보다 무겁고 2번은 1번보다 무겁고 5번은 1번보다 무겁다. 따라서 여기서 추론하면 4번이 1번보다 무겁다는 것을 알 수 있다.
  구슬의 무게 순으로 정렬을 하게 된다면 5개의 구슬을 무게 순으로 내림차순 정렬하면 정확한 등수를 파악하기는 힘드나 1번이 4번째 아니면 5번째에 위치한다는 것을 알 수 있다. 따라서 무게가 중간인 구슬이 될 수 없다.

💡코드(메모리 : 31256KB, 시간 : 172ms)

import sys
input = sys.stdin.readline

N, M = map(int, input().strip().split())
graph = [[False] * (N+1) for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().strip().split())
    graph[a][b] = True # a가 b보다 무겁다.

for k in range(1, N+1):
    for a in range(1, N+1):
        for b in range(1, N+1):
            if graph[a][k] == True and graph[k][b] == True:
                graph[a][b] = True

answer = 0
mid = N // 2
for a in range(1, N+1):
    left_cnt = 0
    right_cnt = 0
    for b in range(1, N+1):
    	# a가 b보다 무거운 경우 : right_cnt에 +1
        if graph[a][b]:
            right_cnt += 1
        # b가 a보다 무거운 경우 : left_cnt에 +1
        elif graph[b][a]:
            left_cnt += 1
    # 만약 무거운 경우의 경우의 수와 가벼운 경우의 경우의 수가 중간값보다 크게 나온다면?
    # 무게가 중간인 구슬이 될 수 없다는 의미가 된다.
    if mid < right_cnt or mid < left_cnt:
        answer += 1
print(answer)

💡소요시간 : 34m