백준 2617_구슬찾기

구슬찾기(백준 2617)

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

DFS를 낮은 ‘구슬’과 높은 ‘구슬’로 각각 나누어 돌리는 방식을
사용하였다
각각의 구슬 개수가 ‘총 구슬개수 / 2’를 넘어가면
해당 구슬은 ‘중간’에 올 수 없으므로
count를 올려주었다

Code

import sys
from collections import deque
sys.setrecursionlimit(10**8)

inp = sys.stdin.readline

n, m = map(int,inp().split())
hevParent = [[] for _ in range(n)]
ligChild = [[] for _ in range(n)]
for i in range(m):
    heavy, light = map(int,inp().split())
    hevParent[light-1].append(heavy - 1)
    ligChild[heavy-1].append(light - 1)

for i in range(n):
    hevParent[i] = set(hevParent[i])
    ligChild[i] = set(ligChild[i])

def dfs(start)->bool:
    hCount = [0]
    lCount = [0]

    stack = [(start,-1)]
    hvisit = [False for _ in range(n)]
    lvisit = [False for _ in range(n)]

    while stack:
        currNode, fMode = stack.pop()
        if fMode == -1:
            if check(stack,currNode,hevParent,hCount,hvisit,1) == True:
                return True
            if check(stack,currNode,ligChild,lCount,lvisit,0) == True:
                return True
        elif fMode == 1:
            if check(stack,currNode,hevParent,hCount,hvisit,fMode) == True:
                return True
        else:
            if check(stack,currNode,ligChild,lCount,lvisit,fMode) == True:
                return True

    return False

def check(stack : list,currNode,compares, Count,visit,check)->bool:
    visit[currNode] = True
    for i in compares[currNode]:
        if visit[i] == False:
            visit[i] = True
            Count[0] += 1
            if Count[0] >= n/2:
                return True
            stack.append((i,check))
    return False


answer = 0
for i in range(n):
    if dfs(i):
        answer+=1

print(answer)

해결 아이디어

1. 들어오는 데이터를 각각
   무거운 인접리스트, 가벼운 인접리스트에
   넣어준다
   
2. 각 노드마다 해당 데이터의 각 인접리스트에서
   발견된 노드의 개수가 ‘전체 개수 / 2’ 이상이면
   해당 노드는 중간에 올 수 없다는 뜻이므로
   True를 반환하고 answer += 1 해준다
   
3. 모든 노드에 DFS를 한번씩 돌려준다