[BOJ/python] 2617: 구슬 찾기

문제

✔️ gold 4
그래프 이론
그래프 탐색
깊이 우선 탐색
최단 경로
플로이드–워셜

문제 흐름

문제를 풀기 위해 먼저 무게순 정렬에서 중간이 될 수 없는 구슬의 조건을 알아야한다.
내가 세운 조건은 다음과 같다.

어떤 구슬 X 보다 큰 구슬, 또는 작은 구슬이 전체 구슬 수의 반 이상이면 구슬 X는 중간 구슬이 될 수 없다.

여기서 주의할 점은 큰 구슬과 작은 구슬은 따로 체크해줘야 한다는 점이다.
이를 위해서 두개의 그래프에 각각 저장했다.
하나는 큰 구슬이 작은 구슬을 가리키도록 했고, 다른 하나는 작은 구슬이 큰 구슬을 가리키도록 했다.
DFS를 통해서 모든 노드(구슬)에 대해서 탐색을 진행했고, 해당 노드가 탐색한 노드의 수가 전체 구슬 수의 반 이상이라면 카운트해줬다.
두개의 그래프에 대해서 각각 위와 같이 DFS를 진행한 뒤 결과값을 합하여 출력했다.

플로이드-워셜 알고리즘을 통해 해결할까 생각도 했지만 아무래도 시간복잡도가 큰 편이어서 문제에서 주어지는 간선의 수가 비교적 작은 편인 것 같아 DFS 방식을 선택했다.

코드

# 구슬 찾기
# graph

import sys
input = sys.stdin.readline

def dfs(g: list):
    n = len(g)
    res = 0
    for s in range(1, n):
        st = [s]
        vst = [0 for node in range(n)]
        vst[s] = 1
        cnt = 0
        while st:
            x = st.pop()
            for nx in g[x]:
                if vst[nx]:
                    continue
                st.append(nx)
                vst[nx] = 1
                cnt += 1
        if cnt >= n//2:
            res += 1
    return res


if __name__ == "__main__":
    n, m = map(int, input().split())
    g_1 = [[] for node in range(n+1)]
    g_2 = [[] for node in range(n+1)]
    for compare in range(m):
        a, b = map(int, input().split())
        g_1[a].append(b) # 무거움 -> 가벼움
        g_2[b].append(a) # 가벼움 -> 무거움

    res_1 = dfs(g_1)
    res_2 = dfs(g_2)
    result = res_1 + res_2
    print(result)

마무리

이 문제도 그래프다!! 라고 알고 푼게 아니면 그래프로 생각하고 풀었을까 싶다.
이전에 푼 코드를 보니 DFS로 풀었는데, 이번 풀이에서 수행 시간이 반으로 감소해서 확인해봤다.
이전에는 dfs를 개별적인 함수로 구현하고, 그를 모든 노드에 대해서 돌리는 함수를 또 따로 구현했다.
아무래도 함수호출이 잦아져서 시간도 좀 더 소요된 것 같다.
그리고 모든 노드에서 거쳐가는 노드의 수를 구한 뒤 다시 그 결과를 순회하며 일정 값 이상인지 확인하는 식으로 구성된 부분도 시간이 걸렸을 것 같다.