[프로그래머스] Lv3 - 여행경로

프로그래머스 코딩테스트 고득점 Kit - 깊이/너비 우선 탐색(DFS/BFS)

• Lv 3. 여행경로 (Python)
  https://school.programmers.co.kr/learn/courses/30/lessons/43164

Code

# from collections import deque
from collections import defaultdict

def solution(tickets):
    answer = ["ICN"]
    d = defaultdict(list)   # 리스트를 value로 갖는 딕셔너리 생성

    # key는 출발지, value에는 도착지들 리스트
    for ticket in tickets:
        d[ticket[0]].append(ticket[1])

    # 알파벳 내림차순 정렬
    # ["SFO", "ATL"] 이런 식으로 정렬되기 때문에 나중에 d[top].pop() 으로 알파벳 순서가 앞서는 나라부터 탐색할 수 있음
    for key in d.keys():
        d[key].sort(reverse = True)

    stack = ["ICN"]     # ICN 부터 시작
    path = []

    while stack:
        top = stack[-1]

        if not d[top] or len(d[top]) == 0:  # value가 존재하지 않거나 해당 나라가 출발지인 티켓이 없다면 stack.pop() 해서 path에 넣어준다
            path.append(stack.pop())

        else:
            stack.append(d[top].pop())      # 가장 마지막에 있는 value를 (알파벳 순서가 앞서는 나라) pop해서 stack에 넣어준다

    return path[::-1]   # path를 뒤집어주면 정답

from collections import defaultdict
import copy

def solution(tickets):
    answer = []

    graph = defaultdict(list)

    for i in range(len(tickets)):
        graph[tickets[i][0]].append(tickets[i][1])
        graph[tickets[i][0]].sort()

    print(graph)

    def dfs(depart, route):
        route.append(depart)

        for i in range(len(graph[depart])):
            if (graph[depart][i] == 0):     # 방문한 곳이라면 건너뛰기
                continue
            else:
                arrive = graph[depart][i]   # 해당 출발지에서 갈 수 있는 도착지
                graph[depart][i] = 0        # 방문 처리

                tmp = dfs(arrive, route)    # 해당 루트로 갈수있는 곳까지 가보기

                if (len(tmp) == len(tickets) + 1):      # 만약 모든 티켓을 사용했다면 -> 일단 result에 추가
                    result.append(copy.deepcopy(tmp))

                # 백트래킹 (되돌려놓기, 다음 루트를 위해)
                route.pop()
                graph[depart][i] = arrive

        return route

    result = []
    dfs("ICN", [])
    
    result.sort()
    answer = result[0]

    return answer

풀이 및 해설

두번째 코드가 DFS+백트래킹 재풀이

• copy 안써서 2시간 날림
  • result.append(tmp) 만 하고 → 백트래킹 하면 → result 안에 들어가있는 값도 바뀜 (할당된 메모리 주소가 같아서 그렇다)
• 중요한점 : 모든 티켓을 사용해서 가야함 !!!!
  → 중간에 잘못된 루트에 직면해서 모든 티켓을 소진하지 않는 루트라면 → 그 경로로는 갈 수 없음 !!!!
• 해당 루트로 갈 수 있는 곳까지 가보기 → 모든 티켓 쓰는거 아니면 → 되돌려놓기 (백트래킹)

깔끔 DFS 코드

from collections import defaultdict

def solution(tickets):
    answer = []

    # 그래프 생성
    graph = defaultdict(list)

    for i in range(len(tickets)):
        graph[tickets[i][0]].append(tickets[i][1])
        graph[tickets[i][0]].sort()

    # DFS 탐색
    def dfs(tickets, route, N, visited):
        if (len(route) == N + 1):   # 현재 모든 티켓을 사용한만큼의 길이라면 -> return
            return route

        for i in range(N):
            if (visited[i] == 0 and tickets[i][0] == route[-1]):    # i번째 티켓을 사용하지 않았고 and 마지막 도착지가 현재 출발지라서 존재하는 티켓을 사용 가능할 때
                visited[i] = 1      # 티켓 사용 처리
                tmp = dfs(tickets, route + [tickets[i][1]], N, visited)     # 갈 수 있는데까지 탐색
                visited[i] = 0      # 다시 반환
                if (tmp):
                    return tmp

    N = len(tickets)
    visited = [0 for _ in range(N)]

    tickets.sort()
    r = dfs(tickets, ["ICN"], N, visited)

    print(r)
    answer = r

    return answer

What I learned

▶️ defaultdict()

참고 : https://www.daleseo.com/python-collections-defaultdict/

• 딕셔너리의 기본값을 설정해주는 메서드
• 모든 키에 대해서 값이 없는 경우 자동으로 생성자의 인자로 넘어온 함수를 호출하여 그 결과값으로 설정

아래는 list형식을 딕셔너리의 value 기본 값으로 설정하는 예

from collections import defaultdict

routes = defaultdict(list)

# tickets 리스트를 돌면서, 
# 맨 앞에 있는 값을 key, 그 뒤로 오는 값들을 리스트 형식으로 해서 value로 넣어주기
for ticket in tickets:
	d[ticket[0]].append(ticket[1])

# 결과

routes = {
    "ICN": ["SFO", "ATL"],
    "SFO": ["ATL"],
    "ATL": ["ICN", "SFO"]
}

참고

https://python101.tistory.com/entry/파이썬-DFS-구현
https://gurumee92.tistory.com/165
https://yuna0125.tistory.com/217
https://wwlee94.github.io/category/algorithm/bfs-dfs/travel-route/
https://school.programmers.co.kr/learn/courses/30/lessons/43164/solution_groups?language=python3