[프로그래머스][KAKAO_인턴][2020] 동굴 탐험

프로그래머스 코딩테스트 고득점 Kit의 문제입니다.

https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

코딩테스트 연습

 

문제

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

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

 

내가 작성한 코드

from collections import defaultdict, deque
def solution(n, path, order):
    graph = defaultdict(list)
    preorder = defaultdict(lambda: -1)
    release = defaultdict(lambda: -1)
    for _from, _to in path:
        graph[_from].append(_to)
        graph[_to].append(_from)
    for A, B in order:
        release[A] = B
        preorder[B] = A

    visited = [2] * n
    q = deque()
    if preorder[0] < 0:
        q.append(0)
    
    while q:
        s = q.popleft()
        visited[s] = 0

        for e in graph[s]:
            if visited[e] == 2:
                if preorder[e] > 0:
                    visited[e] = 1
                    continue
                visited[e] = 0
                q.append(e)
                to_release = release[e]
                if to_release > 0:
                    if visited[to_release] == 1:
                        q.append(to_release)
                    else:
                        preorder[to_release] = -1

    return sum(visited) == 0

• 트리
  
  • 루트 노드가 정해져있음
  • 두 방을 잇는 길은 단 하나
  • 즉, 루트부터 단방향으로 탐색 가능
• 위상정렬
  • 탐색된 노드가 우선탐색이 필요한 노드가 있을 경우 ( A -> B )
    - 노드(A)가 탐색이 되었음을 표시 후(1) queue에 push하지 않음
  • 탐색된 노드가 우선탐색으로 필요한 노드일 경우 ( A -> B )
    - 노드(A)가 탐색되었을 경우(1), queue에 push
    - 탐색되지 않았을 경우(2), 탐색이 필요한 노드(B)가 없음으로 표시

 

다른 사람이 작성한 코드

None

• 하나의 테스트케이스가 실패하여 찾아보니, 시작 노드가 다른 노드의 탐색을 필요로 하는 케이스가 존재한다

https://jellyinghead.tistory.com/41

[프로그래머스] 동굴 탐험 (자바)

 

기억해야할 것

• 생각보다는 어렵지 않게 풀었다
• 무언가 다른 조건이 가미되면 어려울 수 있겠다