[프로그래머스] 여행경로 (DFS)

사용 언어: Python3

문제

여행경로

풀이

DFS 🌟

def solution(tickets):
    
    def DFS(start, path):
        if sum(used) == len(tickets): # ✅ 모든 티켓을 사용했을 때
            res.append(path)
            return
        # if len(path) == len(tickets) + 1: # ✅ 경로가 티켓 수보다 1크면 모든 티켓 사용한 것
        #     res.append(path)
        #     return
        for i, tck in enumerate(tickets):
            # tck[0]은 출발 공항, tck[1]은 도착 공항
            if not used[i] and start == tck[0]:
                used[i] = 1
                DFS(tck[1], path + [tck[1]]) # ✅ path에 도착공항 누적
                used[i] = 0
    
    res = []
    used = [0] * len(tickets) # 티켓 사용 여부
    DFS("ICN", ["ICN"]) # ✅ 항상 "ICN" 공항에서 출발합니다.

    res.sort()
    return res[0]

주의 🚨 - 이렇게 하면 안됨!

아래 BFS 풀이 방법처럼 DFS에서도 used를 파라미터로 같이 전달해보았는데, 테스트케이스 4개 중 1개에서 런타임에러가 난다..ㅜ

def solution(tickets):
    
    def DFS(start, path, used):
        if len(used) == len(tickets): # 모든 티켓을 사용했다면
            res.append(path)
            return
        for src, dest in tickets:
            if (src, dest) in used: # 이미 사용한 티켓이라면
                continue
            if src == start:
                DFS(dest, path + [dest], used + [(src, dest)]) # 2. 도착 공항을 누적
    
    res = []
    DFS("ICN", ["ICN"], []) # 1. 경로에 출발 공항 미리 append
    res.sort()
    return res[0]

BFS

from collections import deque

def solution(tickets):
    q = deque()
    q.append(["ICN", ["ICN"], []]) # ✅ airport, path, used 로 전달하기
    res = []
    while q:
        cur, path, used = q.popleft()
        if len(path) == len(tickets) + 1:
            res.append(path)
            continue
        for i, tck in enumerate(tickets):
            if tck[0] == cur and not i in used: # ✅ 사용하지 않은 티켓이면
                q.append([tck[1], path + [tck[1]], used + [i]])
    return sorted(res)[0]

참고

BFS - 함수로 분리 (0530 추가)

from collections import deque

def solution(tickets):
    def BFS():
        while q:
            start, path, used = q.popleft()
            if len(path) == len(tickets) + 1: # ✅ 모든 티켓을 사용했다면
                res.append(path)
                continue
            for i, tck in enumerate(tickets):
                if tck[0] == start and not i in used: # ✅ 사용하지 않은 티켓이면
                    q.append([tck[1], path + [tck[1]], used + [i]])
                    
    res = []
    q = deque()
    q.append(["ICN", ["ICN"], []]) # ✅ (airport, path, used) 로 큐에 append
    BFS() # ✅ BFS
    res.sort()
    return res[0]

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기