문제

동굴 탐험

접근

호율성 테스트를 통과하기 힘들었다.

처음에 기본 골격은 BFS로 잡고 시작했다.
효율성 맞추려고 하다보니 BFS랑 DFS랑 조금 짬뽕된 느낌..

인접 리스트로 그래프를 표현해준 후, pre_visit라고 해서 선행해야 하는 노드들을 담아주었다.
0번 노드에 선행노드가 필요하다면 시작도 못하므로, 항상 False이다.

그리고 0번 노드부터 BFS를 시작한다.
기본 토대는 BFS 그대로지만 조금 검사해야할 조건이 있다.
큐에서 노드를 꺼낸 후, 해당 노드에 선행 노드가 있는지 체크한다.
선행 노드가 방문을 완료했다면 기존 BFS를 수행하며, 선행 노드가 아직 방문 이전이라면
remind라는 큐에 해당 노드를 따로 담아논다.
이렇게 큐가 빌 때까지 수행하고나면 remind를 체크해본다.
remind에 아무것도 없으면 모든 노드를 정상적으로 방문했으니 True를 반환한다.
remind에 무언가 남았으면 선행 노드 때문에 방문을 못한 노드가 남았다는 의미이다.
remind를 메인 큐로 삼고 다시 BFS를 수행한다.
이 것을 q와 remind가 모두 빌 때까지 반복하면 된다.

그럼 이제 모든 노드에 방문이 불가능한 경우에 대해 생각해보자.
이 경우는 전달받은 초기 q와 remind가 동일하면 결국 해당 BFS에서 아무런 노드도 방문에 성공하지 못했다는 의미이다.
q는 while문을 돌면서 계속 pop을 해주기 때문에, 복사 해놓지 않는 이상 수행이 완료된 후 기존 q와 비교가 불가능하다.
BFS while문의 루틴은 크게 다음과 같다.

1. q에서 노드를 꺼낸다.
2. 노드의 선행노드 방문 이전이라면 remind에 노드를 담고 1번으로 돌아간다.
3. 노드의 선행노드를 이미 방문했으면 해당 노드와 인접한 노드들을 q에 담는다.

나는 isSame이라는 flag를 하나 만들어두고, 위의 루틴에서 2번과 3번 사이에 isSame = False라고 해주었다.
즉, 3번 과정에 한번도 도달하지 못했다면, q와 remind는 동일할 것이다.
따라서 isSame은 True상태를 유지할 것이고, 이는 모든 노드의 방문이 불가능하기 때문에 False를 반환한다.

다 맞췄는데 효율성 테스트 10번에서 자꾸 시간초과가 떳다…
위의 순환이 계속 반복하며 마지막 노드만 하나씩 조건이 풀릴 경우 굉장히 오래걸릴 것이다.
그래서 원래 BFS는 큐의 마지막에 원소를 담아주는데, 그걸 맨 앞에 담아줬더니 통과했다….

사실 효율성 테스트 10번에서 재귀 깊이 런타임 에러가 발생했어서 그거보고 대충 때려맞췄다..
아마 처음부터 BFS가 아니고 그냥 DFS로 구현했었다면..

코드

• 파이썬 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

from collections import deque
import sys
sys.setrecursionlimit(10**6)
def bfs(adj, visit, pre_visit, q):
    remind = deque()
    isSame = True
    while q:
        node = q.popleft()
        if visit[pre_visit[node]]:
            pre_visit[node] = 0
        else:
            remind.append(node)
            continue
        isSame = False
        for item in adj[node]:
            if visit[item] == 0:
                q.appendleft(item)
                visit[item] = 1
    if isSame:
        return False
    if remind:
        return bfs(adj, visit, pre_visit, remind)
    else:
        return True

def solution(n, path, order):
    adj = [[] for _ in range(n)]
    visit = [0] * n
    pre_visit = [0] * n
    q = deque()
    q.append(0)
    visit[0] = 1
    for a, b in path:
        adj[a].append(b)
        adj[b].append(a)
    for a, b in order:
        pre_visit[b] = a

    if pre_visit[0]:
        return False
    return bfs(adj, visit, pre_visit, q)