[프로그래머스] 동굴탐험

https://school.programmers.co.kr/learn/courses/30/lessons/67260

프로그래머스

 

🤔 문제분석

📝 문제요약

트리구조로 n개의 방이 주어지고, 방문순서가 주어질때 방문 순서에 따라서 0번인 루트노드로부터 모든 노드까지 주어진 방문 순서에따라서 방문이 가능한지 확인하는 문제이다.

🎯 필요한 개념

• 트리에서의 탐색
• 너비우선탐색

✅ 알고리즘

1. 양방향 그래프임으로 주어진 간선을 초기화 한다.
2. 먼저방문해야 할 노드를 기억해준다.
3. 0번 노드로부터 탐색을 시작한다.
4. 주어진 간선을 통하여 너비우선탐색으로 다음 노드를 방문해아나간다.
   1. 만약, 선행노드를 방문하지 않았더라면 나중에 방문해야할 노드로 표시해준뒤 무시한다.
   2. 선행노드가 없는 경우에는 그냥 방문한다.
5. 나중에 방문해야하는 노드를 현재 방문되고 있는 노드에서 4번 a 조건에서 표시한 방문해야할 노드가 존재할 경우 방문처리를 추가로 해준다.
6. 모든 노드가 방문이 가능한지 리턴한다.

반드시 방문해야하는 방은 없거나 또는 1개 이기때문에 선행 작업이 끝나는 노드가 방문하면서 직전에 방문해야할 노드를 표시를 확인만 해준다면 모든 경우를 탐색 할 수 있다.

💻 코드

# <https://school.programmers.co.kr/learn/courses/30/lessons/67260>

from collections import deque, defaultdict

def solution(n, path, order):
    graph = defaultdict(list)
    for a, b in path:
        graph[a].append(b)
        graph[b].append(a)
    
    pre_visit = [-1] * n
    post_visit = [-1] * n
    
    for a, b in order:
        pre_visit[b] = a
    
    if pre_visit[0] != -1:
        return False
    
    visited = [False] * n
    q = deque([0])
    visited[0] = True
    
    while q:
        node = q.popleft()
        
        for neighbor in graph[node]:
            if not visited[neighbor]:
                # 선행 방문 노드가 있는 경우, 아직 선행 노드를 방문하지 않았다면
                if pre_visit[neighbor] != -1 and not visited[pre_visit[neighbor]]:
                    # 추후 방문 노드로 설정해준다.
                    post_visit[pre_visit[neighbor]] = neighbor
                    continue
                
                # 방문 처리
                visited[neighbor] = True
                q.append(neighbor)
                
                # 후행 방문 노드가 대기 중인 경우
                if post_visit[neighbor] != -1:
                    next_node = post_visit[neighbor]
                    visited[next_node] = True
                    q.append(next_node)
    
    return all(visited)