99클럽 코테 스터디 34일차 TIL, 프로그래머스 / 여행경로

🔑 오늘의 학습 키워드 dfs, 백트래킹

🔗 문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/43164

 

def solution(tickets):
    n = len(tickets)
    answer = []
    def dfs():
        if len(stack) == n+1 :
            a = [stack[i] for i in range(n+1)]
            answer.append(a)
        for i in range(n):
            if not visited[i] and stack[-1] == tickets[i][0] :
                visited[i] = 1
                stack.append(tickets[i][1])
                dfs()
                visited[i] = 0
                stack.pop()

    for i in range(n):
        visited = [0] * n
        stack = []
        if tickets[i][0] == "ICN":
            visited[i] = 1
            stack.append(tickets[i][0])
            stack.append(tickets[i][1])
            dfs()

    return min(answer)

 

🗒️ 공부한 내용 본인의 언어로 정리하기

🤔 문제를 보고 든 생각

단순히 bfs로 생각해서 인천에서 시작하는 경우로 탐색하면 된다고 생각했다.

 

하지만 방문하는 경우가 같을때 순서가 알파벳순으로 해야해서 그렇게 하면 안된다.

 

dfs로 풀면서 가지치기 해나가는 방식으로 해야겠다고 생각했다.

⏰ 예상 시간 복잡도 O( N * N! )

제한 사항

모든 공항은 알파벳 대문자 3글자로 이루어집니다.
주어진 공항 수는 3개 이상 10,000개 이하입니다.
tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
주어진 항공권은 모두 사용해야 합니다.
만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

😎 알고리즘 개요

1. 입력 및 초기화

• tickets: 항공권 정보가 담긴 리스트, 각 항공권은 [“출발지”, “도착지”]의 형태입니다.

• n: 주어진 항공권의 개수.

• answer: 가능한 모든 경로를 담을 리스트.

 

2. DFS 탐색 함수 정의

• dfs() 함수는 현재 경로를 따라 깊이 우선 탐색을 수행합니다.

• 모든 항공권을 사용한 경우, 즉 len(stack) == n + 1이 되면 현재까지의 경로를 answer 리스트에 추가합니다.

• 반복문을 통해 현재 스택의 마지막 도시와 일치하는 출발지를 가진 항공권을 찾고, 그 항공권을 사용하면서 재귀적으로 dfs()를 호출하여 탐색을 이어갑니다.

 

3. 탐색 시작

• 처음에는 “ICN”에서 시작하는 항공권을 찾아 그 항공권으로부터 탐색을 시작합니다. 이때, 각 항공권의 사용 여부를 체크하기 위해 visited 리스트와 stack을 초기화합니다.

• 모든 탐색이 끝난 후, answer 리스트에 담긴 모든 경로 중 사전순으로 가장 빠른 경로를 반환합니다.

✅ 오늘의 회고

- 이것도 예전에 푼 문제이다.

- 옛날 내 코드는 별로다

 

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL