[Python/파이썬] 백준 2617번 구슬 찾기

https://www.acmicpc.net/problem/2617

코드

from collections import deque
import sys
input = sys.stdin.readline

INF = int(1e9)

n, m = map(int, input().split())
bigger = [[] for _ in range(n+1)]
smaller = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    bigger[b].append(a)
    smaller[a].append(b)


def bfs(start, graph):
    cnt = 0
    visited = [False]*(n+1)
    q = deque([start])
    while q:
        now = q.popleft()
        for nx in graph[now]:
            if not visited[nx]:
                q.append(nx)
                visited[nx] = True
                cnt += 1
    return cnt


answer = 0
for i in range(1, n+1):
    if bfs(i, bigger) > n//2 or bfs(i, smaller) > n//2:
        answer += 1
print(answer)

 

나보다 확실히 큰 구슬이 N//2개 초과로 있거나 확실히 작은 구슬이 N//2개 초과로 있는 경우를 찾으면 되는 문제다.

 

이를 풀기 위해 구슬들 간의 대소관계를 bigger와 smaller라는 배열에 저장했다. 만약 a보다 b가 작다면 bigger[b]에는 a를 추가해주고, smaller[a]에는 b를 추가하여 무엇이 무엇보다 더 작고 큰지를 저장해뒀다.

 

그리고 이 배열 2개를 이용하여 각 구슬마다 BFS를 실행하여 큰 구슬과 작은 구슬이 몇개 있는지 찾았다. 2번의 BFS 중 하나라도 방문한 노드 개수가 N//2를 넘는다면 그건 확실하게 중앙이 아닌 구슬이다.