TIL) (다시 풀어보기) 2617 구슬 찾기

이 글은,
1. 미래의 내가 다시 이 문제를 풀고자 할 때 과거의 내가 어떻게 문제를 해결했었는지 알려주기 위해서
2. 같은 문제를 풀고 있는 사람에게 아이디어를 제공하기 위해서
작성되었습니다.

구슬 찾기

백준 2617 구슬 찾기 : https://www.acmicpc.net/problem/2617

💡 아이디어

• i 보다 가벼운 노드를 담고 있는 lighter 그래프와 i 보다 무거운 노드를 담고 있는 heavier 그래프를 두 개 만들었다.
• bfs() 함수 안에서 노드를 타고 들어가면서 빈 리스트가 나올 때까지 cnt를 더해준다.
• 더해준 cnt가 구슬의 개수 // 2를 초과하면 answer를 1 증가시킨다.

아이디어 자체는 단순하게 떠올릴 수 있는 문제이다.

하지만 bfs를 이용해 아이디어를 코드로 구현해내는데 어려움을 겪었다.

bfs() 함수를 재귀로 사용해 지나는 구슬을 리스트에 저장해 놓고 그 리스트의 len이 구슬의 개수 // 2를 초과하면 answer를 1 증가시키도록 코드를 구현했다.

하지만 지나온 구슬의 리스트를 모두 저장하는 경우 메모리 초과가 발생한다.

메모리 초과가 발생하지 않게 구현하기 위해서는 지나온 구슬의 번호를 저장하지 않고 count만해줘야한다.

• 소스코드

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())
lighter = [[] for _ in range(N+1)]
heavier = [[] for _ in range(N+1)]
total = 0
std = N//2


def bfs(marble, which):
    global total
    queue = deque()
    visited = [False]*(N+1)
    visited[marble] = True
    queue.append(marble)
    cnt = 0
    while queue:
        num = queue.popleft()
        for n in which[num]:
            if not visited[n]:
                visited[n] = True
                cnt += 1
                if cnt > std:
                    total += 1
                    return
                queue.append(n)


for _ in range(M):
    i, j = map(int, input().split())
    lighter[i].append(j)
    heavier[j].append(i)


for marble in range(1, N+1):
    bfs(marble, lighter)
    bfs(marble, heavier)

print(total)

🎃 아쉬운 점
이 문제를 풀면서 아직 DFS, BFS에 대한 이해가 부족하다는 것을 느꼈다.
DFS로 분류되어있는 문제라서 DFS -> 재귀함수 사용 이라는 공식에 갇혀서 문제를 풀었다.
실제로 구현은 BFS로 할 때 더 간단하게 해결되었다.
구슬 찾기 코드는 좀 더 다양한 문제를 풀어보고 다시 돌아와서 풀어봐야 할 것 같다. 그 때는 좀더 명쾌하게 이해되기를🙏