프로그래머스 <여행 경로>

프로그래머스 <여행 경로>

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

프로그래머스

---

여행 경로

주어진 항공권 tickets를 모두 이용해 여행경로를 짠다. 항상 "ICN" 공항에서 출발해야 하며 모든 항공권을 사용해야 한다.

만약 가능한 여행 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 하여라.

tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.

---

문제해결

DFS를 사용하여 풀었다.

문제풀이에 맞게 데이터를 정제하는 것은 오래 걸리지 않았는데 종료 조건을 만드는 게 어려웠다. 파이썬으로 하다보니 헷갈리는 부분이 많았다. 

 

먼저 입력으로 들어오는 tickets 배열의 값을 이용해 항공권 정보를 저장하는 airline(dictionary)을 만들었다. airline은 출발 공항을 key로 하고 그 공항에서 갈 수 있는 공항들의 list를 value로 한다. (문제 조건에서 가능한 여행 경로가 2개 이상일 경우 알파벳 순서가 앞서는 여행 경로를 반환하라고 했기 때문에 처음 찾은 것이 가장 앞서는 여행 경로가 되게 하기 위해  value 값을 sort 하였다.)

 

모든 항공권을 사용해야하기 때문에 방문체크가 필요하다고 판단하여 visit(dictionary)을 만들었다. 만들어진 airline을 이용해 출발 공항을 key로 하고 boolean list를 value로 하는 dictionary를 만들었다.

 

process(start, airline, visit, acc) 재귀 함수

start는 출발 공항이며, airline과 visit은 위에서 만든 데이터들이다. 마지막으로 acc는 여행 경로를 누적하는 list이다.

종료 조건으로 모든 항공권을 사용했는지 검사하고 만약 그렇다면 True를 반환한다.

그렇지 않은 경우에는 start가 airline에서 key가 되는 공항인지 확인했다. 공항 중에는 도착 공항만 되는 경우도 있기 때문에 airline에서 key가 안 될 수도 있기 때문이다. (이거 때문에 런타임 에러가 계속 났다... 만약 이 문제에서 코드를 제출했을 때 테스트케이스 1, 2번이 런타임에러가 난다면 이 부분을 확인해보자.)

 

본격적으로 여행 경로를 구하기 위해서 start에서 갈 수 있는 공항 list(airline[start])를 가지고 for문을 돌렸다.

방문한 곳이라면 넘어가고 그렇지 않은 곳이라면 방문 체크 후 start를 해당 공항으로, acc에 start를 넣고 재귀 호출을 하였다. 이때 acc를 만드는 과정에서 temp 변수에 deepcopy하여 사용하였는데 이렇게 하지 않으니까 잘못된 경로일 경우에 돌아왔을 때 acc가 그대로여야 하는데 잘못된 경로가 들어있는 문제가 있었다. 참조 방법에 대한 문제였는데 아래의 예시를 보고 deepcopy를 써야한다는 것을 깨달았다.

a = [1, 2, 3, 4]
b = a
b.append(5)
print(a) -> [1, 2, 3, 4, 5]

---

코드

import copy
import sys
sys.setrecursionlimit(100000)
def solution(tickets):
    airline = refining(tickets)
    visit = visit_init(airline)
    process("ICN",airline, visit, ["ICN"])
    return answer
# tickets 를 입력으로 받아서 key를 출발 공항 value를 도착 공항 list로 하는 airline(dictionary) 반환
def refining(tickets):
    airline = dict()
    for ticket in tickets:
        temp = airline.setdefault(ticket[0], [])
        temp.append(ticket[1])
        airline[ticket[0]] = temp
    for key in airline:
        temp = airline[key]
        airline[key] = sorted(temp)
    return airline
# airline을 입력으로 받아서 key를 출발 공항 value를 방문 체크하는 list로 하는 visit(dictionary) 반환
def visit_init(airline):
    visit = dict()
    for key in airline:
        visit[key] = [False for _ in range(len(airline[key]))]
    return visit
# 정답을 저장할 global 변수
global answer
answer = None
# 실제로 경로를 구하는 재귀함수
# start: 출발공항 airline: 항공권 정보, visit: 방문 체크, acc: 경로 누적 list
def process(start, airline, visit, acc):
    global answer
    # 모든 곳을 방문했으면 answer를 update하고 True를 반환
    if check(visit):
        answer = copy.deepcopy(acc)
        return True
    # 도착지이기만한 공항이 있을 수 있으므로 airline에 없는 key인 경우 False를 반환
    chk = airline.setdefault(start, [])
    if len(chk) == 0: return False
    # 출발 공항(start)의 도착 공항 list를 보면서 방문하지 않았을 경우 재귀 호출을 진행한다.
    for i in range(len(airline[start])):
        if visit[start][i]: continue
        visit[start][i] = True
        temp = copy.deepcopy(acc)
        end = airline[start][i]
        temp.append(end)
        ans = process(end, airline, visit,temp)
        if ans:
            return True
        visit[start][i] = False
    # for문을 빠져나온 경우는 아직 여행 경로를 찾지 못한 경우이므로 False를 반환
    return False
# visit을 입력으로 받아서 모든 항공권을 사용했는지 check
def check(visit):
    for key in visit:
        for chk in visit[key]:
            if not chk:
                return False
    return True

---

결과

---