프로그래머스 DFS/BFS, 여행경로(Level3) with Python

오늘은 프로그래머스의 코딩 테스트 고득점 Kit에 들어있는 DFS/BFS문제를 풀어보려 합니다.

DFS/BFS는 코딩테스트에 자주 나오는 유형이니 4문제 다 풀어보면 좋을 것 같네요 

오늘 풀어볼 문제는 여행경로입니다.

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

처음 문제를 읽고 레벨3치고는 쉽네? 생각했는데, 테스트 케이스 1번 때문에 생각보다 애를 먹었네요. 그래서 아예 풀이를 갈아엎고 다시 풀었다는.. ㅜㅜ 

 

문제 설명 & 제한사항

 

저의 접근 방식은 이렇습니다.

1. 주어진 배열을 그래프로 만든다. (그래프 만드는 방법은 다양한 방법이 있겠지만, 저는 딕셔너리를 사용해서 인접 리스트 형식으로 만들었습니다.)

2. 큐를 만들고 (출발 노드, [경로]) 넣어준다. (처음엔 출발점이 무조건 'ICN'이기 때문에 ('ICN',['ICN'])을 넣어줬습니다.

3. 경로 찾는 함수 작성, 여기서 한 공항에서 다른공항으로 갈 수 있는 여러 경우의 수가 생기기 때문에 경로 분기 + 재귀가 필요합니다.

4. 가능한 경로를 다 찾은 후, 알파벳 순으로 정렬 & 첫번째 경로 리턴 

-끝- 

파이썬 코드

import collections, copy

def solution(tickets):
	
    # 그래프 만들기
    graph = collections.defaultdict(list)

    for ticket in tickets:
        graph[ticket[0]].append(ticket[1])
	
    # 출발점이 무조건 'ICN'
    queue = collections.deque([('ICN', ['ICN'])])
    result = []
	
    def find_path(graph, queue):
        n, path = queue.popleft()
		
        # 재귀 종료조건
        if len(path) == len(tickets)+1:
            result.append(path) # 완성된 경로 추가
            return

        for m in graph[n]:
            next_graph = copy.deepcopy(graph) # 그래프 깊은 복사
            queue.append((m, path + [m])) # 경로 분기
            next_graph[n].remove(m) # 방문한 공항 삭제
            find_path(next_graph,queue) # 재귀

    find_path(graph,queue)       
    result.sort() # 알파벳순 정렬
    return result[0]

혹시 틀린점이나 잘못된 부분이 있다면 댓글 남겨주시기 바랍니다! 

읽어주셔서 감사합니다 :)