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

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

 

#백준 2617 구슬찾기
import sys
from collections import deque
input = sys.stdin.readline

# N: 구슬 수, M: 비교 횟수
N, M = map(int, input().split())
ans = [False for _ in range(N + 1)]  # 각 구슬이 절대 중간이 될 수 없는지 여부 저장

# 그래프: 무거운 쪽과 가벼운 쪽을 각각 따로 저장
check_heavy_w = [[] for _ in range(N + 1)]  # 자신보다 무거운 구슬들
check_light_w = [[] for _ in range(N + 1)]  # 자신보다 가벼운 구슬들

# 중간값 기준: 자신보다 무겁거나 가벼운 구슬이 절반 이상이면 중간이 될 수 없음
threshold = N // 2 + 1

# 비교 정보 입력
for _ in range(M):
    heavy, light = map(int, input().split())
    check_heavy_w[light].append(heavy)  # light보다 무거운 heavy
    check_light_w[heavy].append(light)  # heavy보다 가벼운 light

# 1. 자신보다 무거운 구슬의 개수가 절반 이상인지 검사 (BFS)
for i in range(1, N + 1):
    visited = [False for _ in range(N + 1)]
    cnt_heavy_w = 0
    visited[i] = True
    q = deque()
    q.append(i)

    while q:
        ball = q.popleft()
        for h_ball in check_heavy_w[ball]:  # 현재 구슬보다 무거운 구슬들 순회
            if not visited[h_ball]:
                visited[h_ball] = True
                cnt_heavy_w += 1
                q.append(h_ball)
    
    # 무거운 구슬 개수가 기준 이상이면 중간이 될 수 없음
    if cnt_heavy_w >= threshold:
        ans[i] = True

# 2. 자신보다 가벼운 구슬의 개수가 절반 이상인지 검사 (BFS)
for i in range(1, N + 1):
    visited = [False for _ in range(N + 1)]
    cnt_light_w = 0
    visited[i] = True
    q = deque()
    q.append(i)

    while q:
        ball = q.popleft()
        for l_ball in check_light_w[ball]:  # 현재 구슬보다 가벼운 구슬들 순회
            if not visited[l_ball]:
                visited[l_ball] = True
                cnt_light_w += 1
                q.append(l_ball)
    
    # 가벼운 구슬 개수가 기준 이상이면 중간이 될 수 없음
    if cnt_light_w >= threshold:
        ans[i] = True

# 중간이 될 수 없는 구슬의 개수 출력
print(sum(ans))

이 문제의 핵심은 그래프를 통해 자신보다 무거운/가벼운 구슬의 수가 몇개인지 체크하고, 갯수가 절반을 초과하는지 확인하는 것이다.

절반을 초과하게되면 절대 중간이 될 수가 없다.

BFS 를 두번사용 해결하였는데, GPT를 통해 BFS 함수를 정의하여 깔끔하게 코드를 정리하였다.

 

#백준 2617 구슬 찾기
import sys
from collections import deque
input = sys.stdin.readline

# 입력 받기
N, M = map(int, input().split())
threshold = N // 2 + 1
heavier = [[] for _ in range(N + 1)]  # 자신보다 무거운 구슬들
lighter = [[] for _ in range(N + 1)]  # 자신보다 가벼운 구슬들

# 비교 정보 입력
for _ in range(M):
    heavy, light = map(int, input().split())
    heavier[light].append(heavy)  # light보다 무거운 heavy
    lighter[heavy].append(light)  # heavy보다 가벼운 light

# 공통 BFS 함수 정의
def bfs(start, graph):
    visited = [False] * (N + 1)
    q = deque([start])
    visited[start] = True
    count = 0
    while q:
        node = q.popleft()
        for neighbor in graph[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                count += 1
                q.append(neighbor)
    return count

# 중간이 될 수 없는 구슬 개수 세기
answer = 0
for i in range(1, N + 1):
    if bfs(i, heavier) >= threshold or bfs(i, lighter) >= threshold:
        answer += 1

print(answer)