순서가 정해진 그래프를 모두 방문할 수 있는지를 물어보는 문제다.
효율성까지 점수를 매기므로, 스택이나 큐를 사용하도록 하자.

간단하게 설명하자면, 시작은 반드시 0부터 하고,
order들을 불러와 첫번째 요소를 먼저방문하여야, 두번째 요소를 방문할 권한이 생긴다.

order = [[1, 2], [4, 5], [3, 6]]

위와 같은 order배열이 존재할 때, 1, 4, 3 정점은 그냥 방문해도 좋지만,
2, 5, 6은 key에 해당되는 원소가 방문되지 않았을 경우 방문할 수 없다.

이 문제는, 푸는 방식이 다양하므로, 해당 해설은 0부터 시작하여 모든 정점들을 방문하는 알고리즘이다.
필자는 위상정렬같은 알고리즘은 잘 모르므로 그건 다루지 않겠다.

먼저, 그래프를 만들어주어야한다.
효율성 때문에라도, 단방향 그래프를 만들어야 할 것 같지만,
나중에 방문변수로 처리해주면 되므로, 양방향그래프로 만들어도 상관없다.

graph = [[] for i in range(n)]

for i, j in path:
    graph[i].append(j)
    graph[j].append(i)

위와 같이 파이썬코드로 간단히 양방향그래프를 구현할 수 있다.
만약 단방향그래프를 구현하려하면, 할 수는 있겠지만, 오히려 시간복잡도와 공간복잡도가 증가할 것으로 보인다.

다음은, visited변수를 선언해준다.
단순히 해당 정점을 방문했는지 확인하는 용도로 사용하므로,
bool 자료형의 False를 n개 만큼의 배열을 선언하면 된다.

visited = [False] * n

위와 같이 파이썬코드로 나타낸다.

다음은 order배열을 활용하여, 다음 정점을 방문할 수 있는지 없는지를 방문하는 판별할 수 있게 도와주는 변수를 선언한다.

key = [0] * n
lock = [0] * n

for i, j in order:
    key[i] = j
    lock[j] = i

위와 같이 배열로 해도되고, 공간복잡도를 더 잡아먹지만 간단한 해시를 사용하여도 좋다.
key배열은 현재 정점을 방문하고 있을 때, key에 해당되면 lock되어있는 정점을 없애주는 용도이다.
lock배열은 다음 정점을 탐색할 때, lock에 해당되면 탐색하지 않게 제한하는 용도이다.

마지막으로, queue를 사용하여 BFS를 돌려주면 된다. 그런데 순서는 중요하지 않으므로,
Stack를 사용하여도 문제를 푸는데는 지장없다.

여기서 또 중요한 점이 존재한다.
key값을 방문하기전에 lock된 정점을 먼저 탐색할 차례가 올 수 있을 것이다.
이를 위해, visited_lock과 같은 추가변수를 선언하여, lock된 정점을 key보다 먼저방문하게 될 경우,
기록을 해준다.

그 이후, lock을 풀 수 있는 key정점을 방문하였을 때, visited_lock의 후보군에 해당 lock이 존재할 경우,
queue에 추가하여 계속해서 이어서 방문이 가능하도록 만들어야한다.

그렇지 않을 경우, lock된 정점은 한 번 방문하고 queue에서 해당정점이 빠져나오게 되어, key에 의해서 해당 lock정점이 방문이 가능할 수 있음에도 queue에 추가된 정점이 존재하지 않으므로, 그냥 방문하지 못하고 종료하게 된다.
사실 문제를 푸는데는 이 아이디어가 매우 중요한 부분이다.
이걸 모른다면, 다른 방법으로도 풀 수 있긴한데... 많이 복잡하고, 재귀문을 작성하다가 머리도 같이 재귀호출당해,
포기할 확률이 높지 않을까 싶다.

내가 생각한 가장 쉬운 풀이를 해설로 작성해보았다.
역시 레벨4는 많이 어렵다.