[프로그래머스] 43164번 여행경로 (2번 테케 틀린 경우)

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

처음에는 단순히 dfs로 풀면되겠다고 생각을 하고, 풀기 시작했다. 그런데 계속 2번 테스트 케이스를 틀렸는데, 그 이유가 출발지가 같은 티켓이 두 개가 있을 경우를 고려하지 않았기 때문이였다.

가능한 경로가 2가지가 있으면 알파벳 순으로 앞서는 경로를 반환하는 것은 맞지만 위의 예시처럼 INC->AAA->BBB->AAA->BBB 의 경로가 되어버리면 모든 티켓을 소모할 수 없다. 따라서 더 이상 방문할 수 있는 도시가 없을 때 주어진 항공권을 모두 사용하지 못했다면, 다른 경로를 탐색하도록 변경 해주어야했다.

처음 코드

이 방식으로 해버리면 출발지가 ICN인 티켓 중에 도착지의 알파벳 순이 빠른 경우로만 무조건 출발을 하게 되기 때문에 틀리게 된다.

def dfs(path, start, visited, tickets):
    # 모든 티켓을 사용한 경우
    if len(path) - 1 == len(tickets):
        return path

    for i in range(len(tickets)):
        if not visited[i] and start == tickets[i][0]:
            visited[i] = True  # 방문 처리
            path.append(tickets[i][1])  # 목적지 추가

            result = dfs(path, tickets[i][1], visited, tickets)
            if result:
                return result  # 유효한 경로를 찾으면 반환

            path.pop()  # 백트래킹: 마지막 추가한 목적지 제거
            visited[i] = False  # 방문 상태 되돌리기

    return None  # 유효한 경로가 없을 경우

def solution(tickets):
    visited = [False] * len(tickets)
    tickets.sort()  # 알파벳 순으로 정렬
    path = ["ICN"]  # 시작점 추가

    for i in range(len(tickets)):
        if tickets[i][0] == "ICN":
            visited[i] = True  # ICN에서 출발하는 첫 번째 티켓 방문 처리
            path.append(tickets[i][1])  # 첫 번째 목적지 추가

            result = dfs(path, tickets[i][1], visited, tickets)
            if result:
                return result  # 유효한 경로를 찾으면 반환

    return []

수정된 코드

def dfs(path, start, visited, tickets):
    # 모든 티켓을 사용한 경우
    if len(path) - 1 == len(tickets):
        return path

    for i in range(len(tickets)):
        if not visited[i] and start == tickets[i][0]:
            visited[i] = True  # 방문 처리
            path.append(tickets[i][1])  # 목적지 추가

            result = dfs(path, tickets[i][1], visited, tickets)
            if result:
                return result  # 유효한 경로를 찾으면 반환

            path.pop()  # 백트래킹: 마지막 추가한 목적지 제거
            visited[i] = False  # 방문 상태 되돌리기

    return None  # 유효한 경로가 없을 경우

def solution(tickets):
    visited = [False] * len(tickets)
    tickets.sort()  # 알파벳 순으로 정렬
    path = ["ICN"]  # 시작점 추가

    result = dfs(path, "ICN", visited, tickets)  # DFS 호출
    return result if result else []  # 결과 반환