[DFS] 프로그래머스 43164번 여행경로

이번 문제는 DFS와 관련된 문제입니다.

방문 체크의 기준이 하나의 node가 아닌 간선이라는 점이 참신했습니다.

맨 처음 풀었던 풀이와 수정된 풀이를 비교해보겠습니다.

 

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/43164

코딩테스트 연습 - 여행경로

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

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

입출력 예

ticketsreturn

[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]	["ICN", "JFK", "HND", "IAD"]
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]	["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

입출력 예 설명

예제 #1

["ICN", "JFK", "HND", "IAD"] 순으로 방문할 수 있습니다.

예제 #2

["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞섭니다.

---

처음에는 방문 체크를 노드기준으로 생각했다가 한참을 헤맸습니다

문제에는 '주어진 항공권은 모두 사용해야 한다'고 되어있으므로

방문 여부를 공항 기준이 아닌 간선(항공권) 기준으로 생각해야 합니다.

 

두 풀이의 차이점

1) flag 변수의 사용 유무 (수정전: O, 수정후: X)

2) new_visit 변수 사용 유무 (수정전: O, 수정후: X)

 

사실 new_visit 변수를 특별히 만들 필요가 없다는 것을 알고는 혼란이 왔습니다.

취준 때는 C언어(필요한 경우 STL 이용)로 코테를 준비했는데,

두번째 풀이처럼 재귀를 호출할 경우 visit변수의 값이 원치 않는 방향으로 수정되는 경우가 있었기 때문이었죠.

 

(제가 기억하기론) C언어에서는 calling한 함수에 A라는 변수가 있고 called된 함수에 B라는 변수가 있을 때,

A와 B의 주소값이 같은 경우 called된 함수에서 B의 값을 바꿔준다면 A의 값도 이에 따라 바뀌었습니다.

 

따라서 C언어에서 두번째 풀이처럼 코딩을 한다면 called된 함수에서 visit 배열의 값을 수정하게되므로

dfs를 호출하기 전의 visit과 호출 후 visit배열의 값이 상당히 다른 경우가 존재하게 됩니다.

따라서 저는 C언어에서는 첫번째 풀이처럼 그냥 새로운 new_visit 배열을 만들어 visit배열을 복사해서 넘겨주는 방식을 활용했습니다.

 

파이썬에서 visit의 주소값을 찍어봤는데 재귀 과정을 거치는 동안 주소값이 변하지 않더라구요.

하지만 dfs를 호출하기 전의 visit배열의 값과 호출한 후의 visit 배열의 값이 하나밖에 다르지 않다는 점이

아직도 이해가 되지 않습니다.

재귀 과정에서 id(visit) 값이 변하지 않음

이 부분에 대해서는 내일 중으로 한번 더 깊게 공부해봐야 겠네요..!

 

어쨌든 두번째 풀이에서는 deepcopy하는 과정이 없어지게 되므로

결론적으로 수행시간이 줄어들게 됩니다.

 

[처음 풀이]

import copy

flag = False
answer = []

def dfs(path, visit, dict_start_idx, info, total_cnt):
    global flag, answer

    if flag is True:
        return

    if len(path) == total_cnt:
        answer = path
        flag = True
        return

    start = path[-1]

    if start in dict_start_idx:
        idx_start = dict_start_idx[start]
        for i, new_end in enumerate(info[idx_start]):
            if visit[idx_start][i] is False:
                new_visit = copy.deepcopy(visit)
                new_visit[idx_start][i] = True
                dfs(path + [new_end], new_visit, dict_start_idx, info, total_cnt)


def solution(tickets):
    global answer

    dict_start_idx = {}
    num_start = 0
    info = []
    visit = []
    total_cnt = len(tickets) + 1

    for start, end in tickets:
        if start in dict_start_idx:
            info[dict_start_idx[start]].append(end)
            visit[dict_start_idx[start]].append(False)
        else:
            dict_start_idx[start] = num_start
            info.append([end])
            visit.append([False])
            num_start += 1

    for ele in info:
        ele.sort()

    path = ['ICN']

    dfs(path, visit, dict_start_idx, info, total_cnt)

    return answer

 

[수정 후 풀이]

dict_start_idx = {}
info = []
total_cnt = 0


def dfs(path, visit):
    if len(path) == total_cnt:
        return path

    start = path[-1]

    if start in dict_start_idx:
        idx_start = dict_start_idx[start]
        for i, new_end in enumerate(info[idx_start]):
            if visit[idx_start][i] is False:
                visit[idx_start][i] = True
                ret = dfs(path + [new_end], visit)
                visit[idx_start][i] = False

                if ret:
                    return ret


def solution(tickets):
    global dict_start_idx, info, total_cnt

    visit = []
    total_cnt = len(tickets) + 1
    num_start = 0

    for start, end in tickets:
        if start in dict_start_idx:
            info[dict_start_idx[start]].append(end)
            visit[dict_start_idx[start]].append(False)
        else:
            dict_start_idx[start] = num_start
            info.append([end])
            visit.append([False])
            num_start += 1

    for ele in info:
        ele.sort()

    path = ['ICN']

    answer = dfs(path, visit)

    return answer