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

여행경로

level3-DFS-여행경로

from collections import defaultdict
def solution(tickets):
    n = len(tickets)
    data =tickets
    
    g = defaultdict(list)
    ch = defaultdict(list) #중복 체크도 딕셔너리로
    
    for i in range(n):
        k, v = data[i][0], data[i][1]
        g[k].append(v) #해당 딕셔너리에 k값에 대응하는 value가 비어있으면 빈 리스트 만들고 v추가.
        ch[k].append(0)
    #알파벳 순이니까 value를 기준으로 오름차순
    for k,v in g.items():
        v.sort()
    
    res = ["ICN"]
    def DFS(L, now):
        if L == n+1: #전부 다 확인. 종료조건
            # tmp = []
            # for x in res:
            #     tmp.append(x)
            # result.append(res[:])
            result.append(res[:])
            # result.append(tmp)
        else: #계속 가야함
            for i in range(len(g[now])):
                if ch[now][i] == 0: #아직 해당 문자열 노드를 아직 방문하지 않았다면
                    ch[now][i] = 1
                    node = g[now][i] #인접노드
                    res.append(node)
                    DFS(L+1, node)
                    res.pop()
                    ch[now][i] = 0
        
    result = []
    DFS(1,"ICN") 
    return result[0]
    

문자열 노드

이 문제처럼 노드의 값이 문자열인 경우 defaultdict를 사용하여 인접리스트를 만들자. 그리고 인접 노드들을 추가해준 후, 방문 체크하는 리스트 역시 defaultdict(list)로 만드는 것이 편하다.
이렇게 해서 그래프를 만들었다면 이제 원래 하던 방식대로 경로를 구해주면 된다.

코멘트

문자열 노드로 인접리스트 만들기. 다시 풀어봐야 함.
이 문제에서 핵심은 백트랙킹을 반드시 해줘야만 한다. 왜냐하면 무조건 경로의 우선적인 것부터 들어간다고 해서 최종적으로 모두 탐색할 수 있는 것이 아니다. 뒤에 있는 경로 먼저 탐색해야 도달할 수도 있기 때문. 그렇기에 백트랙킹 시 원상복구 과정이 필요했다 !!

🎈 다시 풀어봄

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
from collections import defaultdict
def solution(tickets):
    n = len(tickets)
    data =tickets

    g = defaultdict(list)
    ch = defaultdict(list) #중복 체크도 딕셔너리로

    for i in range(n):
        k, v = data[i][0], data[i][1]
        g[k].append(v) #해당 딕셔너리에 k값에 대응하는 value가 비어있으면 빈 리스트 만들고 v추가.
        ch[k].append(0)
    #알파벳 순이니까 value를 기준으로 오름차순
    for k,v in g.items():
        v.sort()

    res = ["ICN"]
    def DFS(L, now):
        if L == n+1: #전부 다 확인. 종료조건
            tmp = []
            for x in res:
                tmp.append(x)
            result.append(tmp)
        else: #계속 가야함
            for i in range(len(g[now])):
                if ch[now][i] == 0: #아직 해당 문자열 노드를 아직 방문하지 않았다면
                    ch[now][i] = 1
                    node = g[now][i] #인접노드
                    res.append(node)
                    DFS(L+1, node)
                    res.pop()
                    ch[now][i] = 0

    result = []
    DFS(1,"ICN") 
    return result[0]
    ```