[python] 프로그래머스 - 동굴 탐험 (2020 카카오 인턴십)

문제 해결

1. 그래프 문제

2. 주어진 path 로 인접리스트를 만든다.

3. 주어진 order 로 딕셔너리를 만든다.

 (1) a 를 방문해야 b 를 방문할 수 있다.

 (2) a를 키, b를 밸류로 하는 딕셔너리를 만든다 | a를 방문했을 때 b를 방문할 수 있다 라는 것을 찾기 위해|

 (3) b를 키, a를 밸류로 하는 딕셔너리를 만든다 | b를 방문하려고 하는데 a를 이미 방문했는지 알아보기 위해|

 (4) a가 0인 경우(선행 조건이 0번방을 방문하는 것) 이므로 값을 0으로 해준다.)

 (5) b가 0인 경우(0번방을 방문하기 위해 다른 방을 방문하고 와야 하므로 처음부터 방에 들어가지 못한다.)

4. visited 배열(0과 1)을 만든다. 방문했는지 안했는지 알아보기 위해

5. 큐를 만들어 BFS를 한다.

 (1) 지금 방문하려고 하는 방이 선행조건이 완수되지 않았다면 visited를 1이 아닌 2로 바꾼다

 (2) 여기서 2로 바꾸는 이유는 방문할 수 있지만 선행조건이 완수되지 않았기 때문에 잠시 대기를 해둔다고 생각

 (3) 선행조건이 완수된 방이거나 선행조건이 없는 방이면 자연스럽게 그래프 탐색을 해준다.

 (4) 여기서 다음에 방문할 방(neighbor)이 선행조건일 경우

 (5) 이 선행조건 때문에 아까 대기상태인 방이 있다면

 (6) 이 방을 큐에 넣어 방문할 수 있도록 만든다.

 

😢 카카오코딩테스트 마지막 문제 답게 어려웠다. 사실 내가 느끼기엔 경주로 건설이랑 난이도가 비슷한거 같다. 어렵다.

단순히 완전탐색으로 풀 수도 있지만, 역시 효율성테스트에서 문제가 발생한다.

효율을 올리기 위해 디큐를 사용한다. 리스트에서 pop()을 할 경우 시간복잡도가 O(n) 이지만

deque에서 popleft()를 할 경우 시간복잡도가 O(1)이다.

 

현재 자바스크립트를 공부중인데, 자바스크립트로 거의 비슷하게 구현했더니 30번테스트에서 틀렸다. 또 효율성테스트에서 마지막 두문제가 시간초과에 걸렸다. 이거 해결하다가 시간을 너무 소비하고 자료도 없어 다음으로 미루겠다.

효율성테스트 시간초과는 자바스크립트로 디큐(시간복잡도 O(1))을 구현하는 방법을 익혀 문제를 해결할 수 있을것이다.

 

소스 코드

from collections import deque
def solution(n, path, order):
    answer = True
    adj = {n: [] for n in range(n)}
    for s, e in path:
        adj[s].append(e)
        adj[e].append(s)

    precedeA = {}
    precedeB = {}

    for a, b in order:
        precedeA[a] = b
        precedeB[b] = a
        if b == 0:
            return False
        if a == 0:
            precedeA[0] = 0

    visited = [0]*n
    visited[0] = 1

    q = deque()
    q.append(0)

    while q:
        current = q.popleft()
        # 알고보니 아직 못가는 상태
        if current == precedeA.get(precedeB.get(current)):
            visited[current] = 2
        else:
            for neighbor in adj[current]:
                if visited[neighbor] == 0:
                    q.append(neighbor)
                    visited[neighbor] = 1

                    if precedeA.get(neighbor):  # 선행조건 일 때
                        if visited[precedeA[neighbor]] == 2:  # 이 선행조건을 필요로 하는 친구가 준비상태이면
                            q.append(precedeA[neighbor])  # 출발시킨다
                            visited[precedeA[neighbor]] = 1

                        precedeA[neighbor] = 0

    for i in visited:
        if i == 0:
            return False
    return answer


print(solution(9, [[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]]	, [[8,5],[6,7],[4,1]]	))
print(solution(9, [[8,1],[0,1],[1,2],[0,7],[4,7],[0,3],[7,5],[3,6]]	, [[4,1],[5,2]]		))
print(solution(9, [[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]], [[4,1],[8,7],[6,5]]))

 

출처: 프로그래머스

문제: https://programmers.co.kr/learn/courses/30/lessons/67260?language=python3

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

오지 탐험가인 프로도는 탐험 도중 n개의 방으로 이루어진 지하 동굴을 탐험하게 되었습니다. 모든 방에는 0부터 n - 1 까지 번호가 붙어있고, 이 동굴에 들어갈 수 있는 유일한 입구는 0번 방과 연결되어 있습니다. 각 방들은 양방향으로 통행이 가능한 통로로 서로 연결되어 있는데, 서로 다른 두 방을 직접 연결하는 통로는 오직 하나입니다. 임의의 서로 다른 두 방 사이의 최단경로는 딱 한 가지만 있으며, 또한 임의의 두 방 사이에 이동이 불가능한 경우는 없습니다. 탐험에 앞서 이 지하 동굴의 지도를 손에 넣은 프로도는 다음과 같이 탐험 계획을 세웠습니다. 모든 방을 적어도 한 번은 방문해야 합니다. 특정 방은 방문하기 전에 반드시 먼저 방문할 방이 정해져 있습니다. 2-1. 이는 A번 방은 방문하기 전에 반드시 B번 방을 먼저 방문해야 한다는 의미입니다. 2-2. 어떤 방을 방문하기 위해 반드시 먼저 방문해야 하는 방은 없거나 또는 1개 입니다. 2-3. 서로 다른 두 개 이상의 방에 대해 먼저 방문해야 하는 방이 같은 경우는 없습니다. 2-4. 어떤 방이 먼저 방문해야 하는 방이면서 동시에 나중에 방문해야 되는 방인 경우는 없습니다. 위 계획 중 2-2, 2-3, 2-4는 순서를 지켜 방문해야 하는 두 방의 쌍이 A → B(A를 먼저 방문하고 B를 방문함) 형태로 유일함을 의미합니다. 즉, 프로도는 아래와 같은 형태로 방문순서가 잡히지 않도록 방문 계획을 세웠습니다. A → B, A → C (방문순서 배열 order = [...,[A,B],...,[A,C],...]) 형태로 A를 방문 후에 방문해야 할 방이 B와 C로 두 개 또는 그 이상인 경우 X → A, Z → A (방문순서 배열 order = [...,[X,A],...,[Z,A],...]) 형태로 A를 방문하기 전에 방문해야 할 방이 X와 Z로 두 개 또는 그 이상인 경우 A → B → C (방문순서 배열 order = [...,[A,B],...,[B,C],...) 형태로 B처럼 A 방문 후이면서 동시에 C 방문 전인 경우 그리고 먼저 방문해야 할 방과 나중에 방문할 방을 반드시 연속해서 방문해야 할 필요는 없어 A방을 방문한 후 다른 방을 방문한 후 B방을 방문해도 좋습니다. 방 개수 n, 동굴의 각 통로들이 연결하는 두 방의 번호가 담긴 2차원 배열 path, 프로도가 정한 방문 순서가 담긴 2차원 배열 order가 매개변수로 주어질 때, 프로도가 규칙에 맞게 모든 방을 탐험할 수 있을 지 return 하도록 solution 함수를 완성해주세요. [제한사항] n은 2 이상 200,000 이하입니다. path 배열의 세로(행) 길이는 n - 1 입니다. path 배열의 원소는 [방 번호 A, 방 번호 B] 형태입니다. 두 방 A, B사이를 연결하는 통로를 나타냅니다. 통로가 연결하는 두 방 번호가 순서없이 들어있음에 주의하세요. order 배열의 세로(행) 길이는 1 이상 (n / 2) 이하입니다. order 배열의 원소는 [방 번호 A, 방 번호 B] 형태입니다. A번 방을 먼저 방문한 후 B번 방을 방문해야 함을 나타냅니다.