-- 깊이 우선: 한 갈래를 끝까지 내려간 뒤 돌아온다
dfs :: Graph -> Node -> [Node]
dfs g start = go [start] []
where
go [] seen = reverse seen
go (n : st) seen
| n `elem` seen = go st seen
| otherwise = go (g ! n ++ st) (n : seen) -- 이웃을 앞에: 첫 이웃이 먼저 (JS 스택은 reverse 후 push)
-- 재귀로 쓰면 돌아올 자리를 콜 스택이 기억한다
graph = fromList [(0, [1, 2]), (1, [0, 3, 4]), (2, [0, 5]), (3, [1]), (4, [1]), (5, [2])]
dfs graph 0 == [0, 1, 3, 4, 2, 5]