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

programmers.co.kr/learn/courses/30/lessons/67260?language=python3

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

tech.kakao.com/2020/07/01/2020-internship-test/

2020 카카오 인턴십 for Tech developers 문제해설

 

Kakao Tech 블로그에서 해설을 봐도 도무지 감이 안와서 문제풀이를 보고 이해한 후, 다시 코딩해보았다.

이 풀이는 '다른 노드문제들 처럼 DFS로 풀 되, ORDER 순서를 지키지 않은 노드는 stack에 추가하지마세요' 라고 해석할 수 있겠다.

 

1. 다른 노드문제들 처럼 DFS로 풀 되, ORDER 순서를 지키지 않은 노드는 stack에 추가하지마세요

2. ORDER 순서를 지키지 않은 노드는 stack에 추가하진 않지만, AFTER에 넣어주고 나중에 따로 처리해 줄게요

3. stack에서 나온 tmp_node가 AFTER에 있나요? 그렇다면 ORDER순서에 따라 tmp_node 다음에 오는 노드도 stack에 넣어주세요

4. 이렇게해서 모든 노드를 방문할 수 있다면 True를 다 방문하지 못한 채 stack이 끝나버렸다면 False를 반환해주세요

 

###시작 위로 부터는 모두 초기 설정

from collections import defaultdict
def solution(n, path, order):
    before = defaultdict(int)
    after = defaultdict(int)
    nodes = defaultdict(list)

    for i in range(len(path)):
        v1, v2 = path[i][0], path[i][1]
        nodes[v1].append(v2)
        nodes[v2].append(v1)
    
    for i in range(len(order)):
        if order[i][1] == 0:
            return False
        before[order[i][1]] = order[i][0]
    
    stack = [0]
    visited = [False]*n
    
    ###시작
    while stack:
        tmp_node = stack.pop()
        if tmp_node in before and not visited[before[tmp_node]]:
            after[before[tmp_node]] = tmp_node
            continue
        
        visited[tmp_node] = True
        for adj in nodes[tmp_node]:
            if not visited[adj]:
                stack.append(adj)
        
        if tmp_node in after:
            stack.append(after[tmp_node])
    
    return True if False not in visited else False

 

1. 초기설정

    before = defaultdict(int) # order [x, y] 에서 {y: x}
    after = defaultdict(int) #  {x: y}
    nodes = defaultdict(list) # {노드: [연결된노드들]}
    
    for i in range(len(path)): # 각각 연결된 노드값의 정보
        v1, v2 = path[i][0], path[i][1]
        nodes[v1].append(v2)
        nodes[v2].append(v1)
    
    for i in range(len(order)):
        if order[i][1] == 0: # 0은 반드시 가장 먼저 방문해야한다. 
            return False
        before[order[i][1]] = order[i][0]
    
    stack = [0] # 처음시작이 0 이므로
    visited = [False]*n

 

2. 알고리즘(DFS)

    while stack:
        tmp_node = stack.pop()
        
        # tmp_node보다 먼저 방문해야하는 node를 아직 방문안했으면 continue
        if tmp_node in before and not visited[before[tmp_node]]:
            after[before[tmp_node]] = tmp_node
            continue
        
        visited[tmp_node] = True
        for adj in nodes[tmp_node]: 
            if not visited[adj]:
                stack.append(adj)
                
        # tmp_node보다 나중에 방문해야하는 node가있으면 stack에 append
        if tmp_node in after:
            stack.append(after[tmp_node])

 

3. 결과

다 방문할 수 있으면 True, 방문하지 못한 node가 있으면 False를 return 해준다.

  return True if False not in visited else False