1. 문제 설명

동굴 탐험

2. 문제 분석

양방향 그래프를 구현한 뒤 DFS를 통해 시작 노드인 0번 노드부터 출발한다. 정해진 순서에 적힌 노드를 만난다면 (before-after) 순서에 따라 행동한다. 이전에 방문할 노드가 있고 아직 방문하지 않았다면 현재 노드를 방문하기 전에 그 노드를 방문해야 한다. 그렇지 않다면, 연결된 다른 노드들 중 방문하지 않은 노드를 방문한다. 마지막으로 이후에 방문할 노드가 있다면 그것을 우선적으로 방문하기 위해 스택에 추가한다.

• 어려운 문제였다. 딕셔너리를 통해 앞뒤를 판단한 뒤 일반적인 DFS를 사용한다.

3. 나의 풀이

import Foundation

func solution(_ n:Int, _ path:[[Int]], _ order:[[Int]]) -> Bool {
    var nodes = Array(repeating: [Int](), count: n)
    for edge in path {
        let (node1, node2) = (edge[0], edge[1])
        nodes[node1].append(node2)
        nodes[node2].append(node1)
    }
    var visited = Array(repeating: false, count: n)
    var before = [Int:Int]()
    var after = [Int:Int]()
    // check order (after - before) as dict
    var stack = [Int]()
    order.map{before[$0[1]] = $0[0]}
    
    stack.append(0)
    // start
    while !stack.isEmpty {
        guard let curNode = stack.popLast() else { continue }
        
        if let nextNode = before[curNode], !visited[nextNode] {
            // curNode -> nextNode, unvisited at this moment
            after[nextNode] = curNode
            continue
        }
        visited[curNode] = true
        for nextNode in nodes[curNode] {
            // if not visited yet, append at stack
            if !visited[nextNode] {
                stack.append(nextNode)
            }
        }
        
        guard let beforeNode = after[curNode] else { continue }
        // if latter node, back to before one
        stack.append(beforeNode)
    }
    
    for check in visited {
        if !check {
            return false
        }
    }
    // check all of nodes visited or not
    return true
}