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

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

코딩테스트 연습 - 동굴 탐험

 

[알고리즘]

 

일단 그래프상 모든 방을 적어도 한 번씩 방문을 해야 하기 때문에 dfs 탐색을 이용해야겠다는 생각이 먼저 든다

다만 이 문제의 경우에는 order 순서에 맞는 방을 list로 기억을 해두어야한다

 

dfs를 진행하다가 선방문을 해야할 방을 방문하지 않았다면 그 방은 skip후 진행한다

 

그 후 선방문을 해야할 방을 만났다면 바로 후 방문할 방을 재귀로 dfs호출 해준다

 

그럼 해당 dfs가 끝나면 다시 원래 선방문해야하는 방의 루트로 돌아오면서 알고리즘이 진행된다

 

[입출력 예제 1]

n = 9

path = [[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]]

order = [[8,5],[6,7],[4,1]]

 

[진행순서]

 

dfs에서는 pop으로 뽑아낼 것이므로 오른쪽부터 탐색을 진행해준다

 

0 → 7 (6을 먼저 방문해야하므로 6의 후방문으로 7을 저장)

 

0 → 3 → 6 (6을 방문했으므로 7로 점프)

 

7 → 5 (8을 먼저 방문해야하므로 8의 후방문으로 5를 저장)

 

7 → 4 → 7 → 0 → 1 (4는 이미 방문했으므로 그대로 진행)

 

2 → 1 → 8 (6을 방문했으므로 5로 점프)

 

5

 

종료

 

[ Code ]

def dfs(node):
    stack = [node]
    visited[node] = True
    while stack:
        curr = stack.pop() #curr = 현재 노드
        for next in graph[curr]:
            if n_visit[curr]: #후 방문이 있을 경우 점프
                dfs(n_visit[curr])
            if not visited[p_visit[curr]]: #먼저 방문해야할 노드를 방문하지 않았을 경우
                n_visit[p_visit[curr]] = curr #후 방문 list에 저장
                continue
            if not visited[next]: #방문한 적 없는 노드일경우 stack에 추가
                stack.append(next)
                visited[next] = True
 
def solution(n, path, order):
    global graph, p_visit, n_visit, visited
    graph = [[] for _ in range(n)]
    p_visit = [0 for _ in range(n)]
    n_visit = [0 for _ in range(n)]
    visited = [False for _ in range(n)]
    
    #양방향 그래프 생성
    for p in path:
        graph[p[0]].append(p[1])
        graph[p[1]].append(p[0])
        
    #order 적용
    for p in order:
        p_visit[p[1]] = p[0]
        
    dfs(0) #dfs 실행
    
    if sum(visited) == n: #모두 방문했을 경우 True 출력
        return True
    
    return False

 

효율성 까지 통과하는 것을 확인 할 수 있다