[프로그래머스 Lv.3] 여행경로(파이썬)

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

프로그래머스

백트레킹을 정리하기 좋은 문제.

1. 시작을 ICN으로 해준다

-->시작점이 무조건 설정되어있는 문제.

시작점을 ICN으로 해주는 건 기본중의 기본

알파벳 순으로 본다는 말이 있어서

알파벳 순으로 정렬한 뒤

시작점이 ICN인 티켓을 처음으로 선택했습니다.

 

2. 백트레킹이 필요하다

-->알파벳순으로 티켓을 정렬한 후 경로를 고르면,

반례가 등장합니다.

그림에서 간단하게 예를 그렸는데,

AA를 고르면 모든 경로를 못가지만

CC를 고르면 모든 경로를 다 갈 수 있다고 가정해보겠습니다.

그러면 이 때는 알파벳순으로는 AA가 먼저라도 해도

CC를 고르는 것이 맞는 선택입니다.

앞으로 계속 경로를 탐색하면서

이런 경우들이 발생할텐데요

백트레킹을 활용해서

모든 경우를 다 따져주면 됩니다.

 

import sys

sys.setrecursionlimit(10 ** 8)


def dfs(now, cnt, tickets, li, visited):
    global answer
    if cnt == len(tickets):

        tmp = []
        for l in li:
            tmp.append(l)
        answer.append(tmp)
        return
    for i in range(len(tickets)):
        if visited[i]:
            continue

        if tickets[i][0] == now:
            visited[i] = True
            li.append(tickets[i][1])
            dfs(tickets[i][1], cnt + 1, tickets, li, visited)
            visited[i] = False
            li.pop()


answer = []


def solution(tickets):
    global answer

    visited = [False] * len(tickets)
    tickets.sort()

    for i in range(len(tickets)):
        if tickets[i][0] == "ICN":
            visited[i] = True
            dfs(tickets[i][1], 1, tickets, [tickets[i][0], tickets[i][1]], visited)
            visited[i] = False

    return answer[0]

 

dfs문제가 백트레킹을 만나면 난이도가 올라가는 편입니다.

이 문제 하나로 백트레킹을 활용한

깊이 우선 탐색을 정리하기 좋습니다.