python 백준 2617 구슬 찾기

백준 2617번 구슬 찾기

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

2617번: 구슬 찾기

중점 : 구슬을 무게 순으로 뒀을때 절대 가운데로 올 수 없는 구슬의 개수를 찾는 문제다

접근법

1. 구슬이 5개일때 자신보다 3개이상의 구슬이 본인보다 무겁거나 가볍다면 그 구슬을 절대 가운데에 올 수 없다.

2. bfs나 dfs를 이용하여 본인의 자식노드 or 손자노드가 3개이상이면 절대 중간에 올 수 없다.

3. 구슬을 무거운 순으로 한번 정렬하고 가벼운 순으로 한번 정렬한다

import sys
from collections import deque

sys.stdin = open('inputs.text')


marble, m = map(int,sys.stdin.readline().split())
graph1 = [[] for _ in range(marble+1)]
graph2 = [[] for _ in range(marble+1)]
count = 0
mid_count = marble//2 + 1
for _ in range(m):
    a, b = map(int,sys.stdin.readline().split())
## 인접리스트로 간선의 개수를 무거운 순과 가벼운순으로 2가지로 표현 ##
    graph1[b].append(a)
    graph2[a].append(b)

def bfs1(start):
    global count
    visited = []
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.append(node)
            queue.extend(graph1[node])
    if len(visited)>mid_count:
        count += 1
    return visited

def bfs2(start):
    global count
    visited = []
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.append(node)
            queue.extend(graph2[node])
    if len(visited)>mid_count:
        count += 1
    return visited
## 가벼운순서와 무거운순서로 bfs를 돌림 ##
for i in range(1,marble+1):
    bfs1(i)
    bfs2(i)
print(count)