2020 카카오 인턴십 - 동굴탐험(python)

❓ 문제 - 2020 카카오 인턴 동굴탐험 문제 - python 풀이법

출처 

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

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

 

📝 문제해결법 

1. 완전탐색인 BFS 사용

2. A와 B가 연결되어 있으면 graph를 통해 연결된 것을 구현

3. 선행조건(A를 방문해야 B방문가능)을 구현 위해 딕셔너리 표현 사용

• precedeA[a] = b -> a(key)방문하면 b(value)방문 가능
• precedeB[b] = a -> b(key)를 방문하려면 a(value) 방문 필요, precedeB는 선행조건을 쉽게 찾기 위해 사용
• b에 0이 들어오면 모두다 방문 불가하므로 False 반환 (모든 동굴은 0을 통해 방문할 수 있으므로)
• a에 0이 들어오면 (원래 0동굴에 방문해야 다른 곳이 방문 가능하므로) b는 0

4. BFS 실행시에 일단 A방문해야하는데(선행조건) 만족되지 못했을 때 B를 방문했다면 아직 방문하지 못하는 상태이므로 visited[now] = 2

5. graph와 연결된 값들을 중에 visited[x] 값이 0이면 큐에 넣고 방문처리

6. graph와 연결된 값이 A(선행조건, precedeA 값중에 1이상인 값이 존재)이면 이 선행조건을 통해서 방문가능한 값 B가 방문 준비상태(visited 값이 2)이면 그 값을 큐에 넣고 visited 값을 1로 변경(방문처리)하고 그 후 선행조건 없애기

출처 : (https://deok2kim.tistory.com/48)

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

해당 블로그의 풀이 방법과 소스코드를 참고해서 공부하였습니다.

 

 

💻 소스코드 

# python 풀이법
from collections import deque
def solution(n, path, order):
    answer = True
    graph = {n:[] for n in range(n)}
    for x, y in path:
        graph[x].append(y)
        graph[y].append(x)

    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:
        now = q.popleft()
        #알고보니 아직 못 가는 상태
        if now == precedeA.get(precedeB.get(now)):
            visited[now] = 2
        else:
            for x in graph[now]:
                if visited[x] == 0:
                    q.append(x)
                    visited[x] = 1

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

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