백준 10159 파이썬 풀이 bfs

이번 포스팅에서는 백준 10159번 저울문제를 bfs로 푼 방식에 대해 설명하겠습니다.

 

 

백준10159 정답 코드

# 복습 횟수:0, 01:30:00, 복습필요O
import sys
si = sys.stdin.readline 
from collections import deque

N = int(si())
M = int(si())

graph_high = [[] for i in range(N+1)]
graph_low = [[] for i in range(N+1)]

def bfs_high(start, tmp_set: set):
    visited = [0 for i in range(N+1)]

    q = deque()
    q.append(start)
    visited[start] = 1 # 방문 처리 

    while q:
        start = q.popleft()
        
        for val in graph_high[start]:
            if visited[val] == 1: continue

            q.append(val)
            tmp_set.add(val)
            visited[val] = 1 # 방문처리
    return

def bfs_low(start, tmp_set: set):
    visited = [0 for i in range(N+1)]

    q = deque()
    q.append(start)
    visited[start] = 1 # 방문처리

    while q:
        start = q.popleft()

        for val in graph_low[start]:
            if visited[val] == 1: continue

            q.append(val)
            tmp_set.add(val)
            
            visited[val] = 1 # 방문처리

    return

for i in range(M):
    x, y = map(int, si().split())

    graph_high[x].append(y)
    graph_low[y].append(x)

for start in range(1, N+1):
    tmp_set = set()
    
    bfs_high(start, tmp_set)
    bfs_low(start, tmp_set)

    print(N-1 - len(tmp_set))

 

백준10159 풀이

1. 큰 것들만 저장하는 graph_high, 작은 것들만 저장하는 graph_low를 만듭니다.

 

2. tmp_set을 두어 비교 가능한 것들을 저장합니다.

 

 

bfs로 작은 것들을 쭉 탐색하면 비교할 수 있는 대상을 모두 탐색할 수 있고, bfs로 큰 것들을 쭉 탐색하면 비교할 수 있는 대상들을 또한 모두 탐색할 수 있습니다. 작은 게 명확할 때, 큰 게 명확할 때 비교할 수 있는 것이므로 bfs를 두 번 돌려 문제를 해결하였습니다.