동굴 탐험

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

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

from collections import defaultdict
from queue import deque

def solution(n, path, order):
    cave = defaultdict(list) # path 그래프

    for n1, n2 in path: # path 그래프
        cave[n1].append(n2)
        cave[n2].append(n1)

    order_dict, order_reverse_dict = {}, {} # order을 dictionary로 저장
    for f, t in order: # f : 이전 방문, t : 이후 방문
        if t == 0: # 이후 방문이 0이면 탐험 불가능
            return False 
        order_dict[f], order_reverse_dict[t] = t, f

    check = defaultdict(int) # 방 번호 : 탐색하면 1,  거꾸로 탐색 방지
    Q, wt = deque([0]), {} # Q는 탐색할 방번호 저장, wt는 탐색 시도는 했으나 아직 접근 불가능한 방 표시
    while Q:
        cur = Q.popleft()

        if cur in order_reverse_dict: # 현재 탐험 할 방의 이전 방문이 완료되지 않음
            wt[cur] = 1 # 대기방으로 표시
            continue
        
        check[cur] = 1 # 접근한 방 표시
        for n_r in cave[cur]: # 현재 방에서 이어진 방들을 탐색 목록 Q에 저장
            if check[n_r] == 0: # 거꾸로 가는것 방지
                Q.appendleft(n_r)

        if cur in order_dict: # 현재 탐색한 방이 이전 방문 조건일 경우,
            if order_dict[cur] in wt: # 만약 현재 방문이 wt에 있는 방의 제한을 풀어준다면,
                Q.append(order_dict[cur]) # 방금 제한이 풀린 방을 다시 탐색하게 함
                del wt[order_dict[cur]]
            del order_reverse_dict[order_dict[cur]] # order이 해결되었으므로 삭제
            del order_dict[cur]
        
    return len(wt) == 0 # 완료되지 못한 방이 0개이면 모두 탐색한 것.

→ 처음 접근한 풀이로 계속 실패하다가 다른 방식으로 해결함.

try 2 : 실제 동굴 탐험가 이동(room 단위)방식으로 동굴을 탐험하되, order을 고려하게 함

try 1 : dfs로 각 방의 루트를 모두 구한 다음, order을 메인 대상으로 잡고 order을 하나씩 해결하려고 함.

 

 

 

<try 1> : 테스트케이스 일부 시간 초과

from collections import defaultdict

def solution(n, path, order):
    cave = defaultdict(list) # path 그래프
    roots = defaultdict(list) # 각 room의 루트

    for n1, n2 in path: # path 그래프
        cave[n1].append(n2)
        cave[n2].append(n1)

    def dfs(start, path): # 각 room의 루트 저장
        path.append(start)
        roots[start] = path[1:]
        for i in cave[start]:
            if i not in path:
                dfs(i, path)
                path.pop()
    dfs(0, [])

    order_dict, order_reverse_dict = {}, {} # order을 dictionary로 저장
    for f, t in order: # f : 이전 방문, t : 이후 방문
        if t == 0 or t in roots[f]: # 이후 방문이 0이거나, 이전 방문 room의 루트에 이후 방문이 있으면,
            return False # 탐험 불가능
        order_dict[f], order_reverse_dict[t] = t, f
    
    stack = [] # 방문 조건이 충족되지 않은 order를 저장
    while order_dict: # order이 모두 만족될때까지
        if stack: # stack에 저장된 order를 먼저 탐색
            cur = stack.pop()
        else: # stack에 있는 order들이 모두 해결되면 아직 탐색하지 않은 다른 order 가져옴
            cur = order_dict.popitem()
            order_dict[cur[0]] = cur[1]
        for room in roots[cur[0]]: # 현재 order의 (이전 방문)room으로 루트를 따라 탐색 
            if order_reverse_dict.get(room) is not None: # 루트에 있는 room이 이전 방문이 완료되지 않은 room이면,
                if [order_reverse_dict[room], room] in stack: # 현재 order를 방해하는 order가 이미 stack에 존재하면
                    return False                              # stack에 저장된 order들이 순회함. 따라서 탐험 불가능.
                stack.append(cur) # 현재 order를 만족하지 못하므로 우선 stack에 저장
                stack.append([order_reverse_dict[room], room]) # 현재 order를 만족하기 위한 또 다른 order 저장
                break
            if order_dict.get(room) is not None: # 만약 루트에 있는 room이 이전 방문 room이면 해당 order는 고려할 필요 없어짐
                del order_reverse_dict[order_dict[room]]
                del order_dict[room]

    return True