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

[프로그래머스][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

기억해야할 것

생각보다는 어렵지 않게 풀었다

무언가 다른 조건이 가미되면 어려울 수 있겠다

from http://pythaac.tistory.com/241 by ccl(A) rewrite - 2021-09-08 04:26:32