[백준-Python] 작업 : 21937번

🥈 Silver1

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

 

 

✅ 정답코드

import sys
input = sys.stdin.readline

def dfs(idx):
    stack.append(idx)
    visited[idx] = True
    
    while stack:
        cur = stack.pop()
        for i in graph[cur]:
            if not visited[i]:
                stack.append(i)
                visited[i] = True
                answer.add(i)

n, m = map(int, input().strip().split())

graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)

for _ in range(m):
    start, end = map(int, input().strip().split())
    graph[end].append(start)

target = int(input().strip())

stack = []
answer = set()

dfs(target)  # 뒤에서부터 역추적

print(len(answer))

 

이것도 다른 그래프 순회 문제처럼, 그래프에서 이동한 거리를 찾으면 되는 문제인데

생각해보니 이 문제는 최종적으로 해야할 작업의 번호만 있지 출발점을 모르는 상태이다.

 

일단 무작정 graph를 그리고 써보니, 최종목표 작업번호를 찾고, 그 인덱스 번호를 가지고 있는 인덱스를 또 찾고 이런식으로 동작해나가야 되겠다란 생각이 들었다. 즉, 뒤에서부터 역추적 방식을 사용해야한다. 

처음엔 저 index를 생각하니 머리가 아팠지만, 어렵게 생각할것 없이 그래프를 뒤에서부터 순회하면서 인접리스트들을 확인하고 방문하는 현재 노드를 중복방지를 위한 answer라는 set에 넣어주고 최종적으론 answer 개수를 리턴한다.

 

❗️오답의 원인이였던, graph를 생성할때 역추적으로 방향이 달라지기 때문에, 인접리스트 또한 달라진다.