프로그래머스 Lv3 | dfs/bfs | 여행경로

https://school.programmers.co.kr/learn/courses/30/lessons/43164

 

2026.04.02 세상 복잡하게 풀었네 기절

dfs로 처음에 접근했다가 다시 돌아와야 하네 하고 bfs로 바꿨었는데

이런 경우에는 백트레킹을 하면 된다는거!

from collections import deque

def next_where(curr, tickets):
    routes = []
    for idx, (s,e) in enumerate(tickets):
        if s == curr:
            routes.append((idx,e))
    return routes

def bfs(start, tickets, n):
    queue = deque([(start, [start], [])])
    answer_list = []
    while queue:
        curr, answer, visited = queue.popleft()
        if len(answer) == n + 1: # 주어진 항공권 모두 사용함
            answer_list.append(answer)
            
        next_routes = next_where(curr, tickets)
        for n_idx, n_r in next_routes: # 현 위치에서 갈 수 있는 경로
            if (n_idx, curr, n_r) not in visited: # 방문한 적 없는 루트일 때 
                answer_n = answer + [n_r]
                visited_n = visited + [(n_idx, curr, n_r)]
                queue.append((n_r, answer_n, visited_n))
    return answer_list


def solution(tickets):
    # 가능한 경로 담기
    # 가능한 경로가 여러개 있다면 알파벳이 먼저인 경로를 담기 <-- X
    # dfs로 알고리즘 구축
        # 현재 위치에서 갈 수 있는 다음 장소들 배열을 받음
        # 그 배열을 알파벳 순서대로 배열하고 <-- X
        # 각각의 경로 bfs로 접근    
    
    answer_list = bfs("ICN", tickets, len(tickets))
    answer_list.sort()
    return answer_list[0]

 

---

 

백트래킹 문제가 여전히 어렵다 ,, ㅠㅠ 

import sys
sys.setrecursionlimit(10**4)

def dfs(curr, tickets, visited, path, answer):
    if len(path) == len(tickets) + 1:
        answer.append(path[:])
        return
            
    for i in range(len(tickets)):
        if not visited[i] and tickets[i][0] == curr:
            next = tickets[i][1]
            visited[i] = True
            dfs(next, tickets, visited, path + [next], answer)
            visited[i] = False

def solution(tickets):
    answer = []
    visited = [False] * len(tickets)
    
    dfs("ICN", tickets, visited, ["ICN"], answer)
    
    answer.sort()
    return answer[0]

https://school.programmers.co.kr/learn/courses/30/lessons/43164