[백준 2617번] 구슬 찾기 - python

문제 링크

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

 

풀이 

처음에는 프로그래머스의 순위 문제처럼 defaultdict을 사용하여 i보다 무거운 사람과 가벼운 사람을 각각 저장하고 두 dict의 길이 중 하나 이상의 개수가 중간값 이상이면 answer + 1 해주는 식으로 풀었다. 

근데 아무리 구글링 해봐도 이렇게 푼 사람이 없는지 반례를 찾지 못했다. 

from collections import defaultdict 

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

heavy = defaultdict(set)
light = defaultdict(set)

for _ in range(m):
    a, b = map(int,input().split())
    # b보다 무거운 거
    heavy[b].add(a)
    # a보다 가벼운 거
    light[a].add(b)

# b보다 무거운 애들은 b보다 가벼운 애들보다도 무거운 것 
for i in range(1,n+1):
    for l in light[i]:
        heavy[l].update(heavy[i])

for i in range(1,n+1):
    # b보다 가벼운 애들은 b보다 무거운애들보다 가벼운 것 
    for h in heavy[i]:
        light[h].update(light[i])
        
answer = 0 
# 가볍거나 무거운 것의 개수가 중간값보다 많으면 될 수 없음 
for i in range(1,n+1):
    h = len(heavy[i])
    l = len(light[i])
    # 반례 찾다가 혹시나 해서 넣어준 자기 자신은 제외하는 코드
    if i in heavy[i] :
        h -= 1
    if i in light[i]:
        l -= 1
        
    if h >= (n+1)//2 or l >= (n+1)//2:
        answer += 1 

print(answer)

결국 bfs 로 풀었다. 

from collections import defaultdict, deque

def bfs(start):
    visited = [False] * (n+1)
    visited[start] = True
    q = deque()
    q.append(start)
    cnt = 0 
    
    # 무거운 거 개수 구하기
    while q:
        x = q.popleft()

        for i in heavy[x]:
            if not visited[i]:
                visited[i] = True
                q.append(i)
                cnt += 1 
        
        if cnt > n // 2 :
            return True 
        
    visited  = [False] * (n+1)
    
    visited[start] = True
    q = deque()
    q.append(start)
    cnt = 0 
    # 가벼운 거 개수 구하기 
    while q:
        x = q.popleft()

        for i in light[x]:
            if not visited[i]:
                visited[i] = True
                q.append(i)
                cnt += 1 
        
        if cnt > n // 2 :
            return True 
            
    return False 
    
n, m = map(int,input().split())

heavy = defaultdict(list)
light = defaultdict(list)

for _ in range(m):
    a, b = map(int,input().split())
    # b보다 무거운 거
    heavy[b].append(a)
    # a보다 가벼운 거
    light[a].append(b)


answer = 0 

for i in range(1,n+1):
    if bfs(i):
        answer += 1 

print(answer)