백준 21937번 - 작업

작업 문제 바로 가기

풀이 날짜: 2026-03-19

baekjoon 알고리즘 문제 풀이

풀이 코드


from collections import deque
import sys
input = sys.stdin.readline

n,m = map(int, input().split())
graph = [[] for _ in range(n+1)]

for _ in range(m):
    a,b = map(int, input().split())
    graph[b].append(a)

visited = [False] * (n+1)

x = int(input())
stack = [x]
visited[x] = True

while stack:
    now = stack.pop()
    for next in graph[now]:
        if not visited[next]:
            visited[next] = True
            stack.append(next)

print(visited.count(True) - 1)

문제 접근

특정 작업 X를 수행하기 전에 반드시 먼저 수행해야 하는 작업들의 개수를 구하는 문제이다. 입력으로 주어지는 관계는 a b 형태로, 작업 a를 먼저 완료해야 작업 b를 수행할 수 있다는 의미를 가진다. 따라서 단순한 순서 문제가 아니라, 그래프 상에서 특정 노드로 도달 가능한 모든 선행 노드를 찾는 문제로 볼 수 있다.

핵심 아이디어

이 문제의 핵심은 그래프의 간선을 뒤집는 것이다. 원래 입력은 a → b 형태로 주어지지만, 우리는 “X보다 먼저 수행해야 하는 작업”을 찾고 싶다. 즉, … → X 형태의 노드들을 찾아야 하므로 간선을 b → a로 뒤집어 저장한다. 이렇게 하면 X에서 시작하여 DFS 또는 BFS를 수행했을 때 방문되는 모든 노드가 곧 X보다 먼저 수행해야 하는 작업들이 된다.

스택을 활용한 DFS 탐색

이 문제는 최단 거리를 구하는 것이 아니라 단순히 연결된 노드의 개수를 구하는 것이므로 \DFS 또는 BFS 모두 사용 가능하다. 여기서는 재귀 대신 스택을 활용한 DFS를 사용하였다. 스택에 시작 노드 X를 넣고, 꺼내면서 인접 노드를 탐색하며 방문하지 않은 노드를 계속 스택에 넣는다. 이 과정을 통해 X에서 도달 가능한 모든 노드를 탐색할 수 있다.

구현 방식

먼저 인접 리스트 형태로 그래프를 생성한 뒤, 간선을 뒤집어 graph[b].append(a) 형태로 저장한다. 이후 방문 여부를 체크할 visited 배열을 만들고, 시작 노드 X를 스택에 넣어 탐색을 시작한다. 스택에서 노드를 하나 꺼내고, 해당 노드와 연결된 모든 노드 중 아직 방문하지 않은 노드를 방문 처리 후 다시 스택에 넣는 방식으로 DFS를 진행한다.

내가 헷갈렸던 부분

결과 계산 방법

탐색이 끝난 후 visited 배열에는 X를 포함한 모든 방문 가능한 노드가 True로 표시된다. 하지만 문제에서 요구하는 것은 X 자신을 제외한 선행 작업의 개수이므로, visited.count(True) - 1을 통해 최종 결과를 계산한다. 이때 -1을 하는 이유는 시작 노드 X도 방문 처리되어 있기 때문이다.

주의할 점

이 문제에서 가장 중요한 포인트는 간선의 방향을 뒤집는 것이다. 이를 놓치면 X로 도달 가능한 노드를 찾는 것이 아니라, X에서 나가는 노드를 찾게 되어 완전히 다른 결과가 나온다. 또한 재귀 DFS를 사용할 경우 그래프가 깊게 이어져 있을 때 재귀 깊이 제한으로 인해 런타임 에러가 발생할 수 있으므로, 스택을 활용한 반복형 DFS를 사용하는 것이 안정적이다.

Vienna sausage