프로그래머스 여행경로

장장 3시간을 붙들어 메고 있었던 문제다... 처음문제를 접하자마자 DFS를 사용해야겠구나 라고 생각하고, 열심히 코드를 작성했다.

for a in tickets:
        t.add(a[0])
        t.add(a[1])

    cand = list(t)
    cand.sort(key=lambda x:(x[0],x[1],x[2]))
    
    city = {}
    for i in range(len(cand)):
        city[cand[i]] = i
        city[i] = cand[i]
        
    graph = [[] for i in range(len(cand))]
    visited = [[0 for j in range(len(cand))] for i in range(len(cand))]
    
    for t in tickets:
        current, next = t[0], t[1]
        graph[city[current]].append(city[next])

input이 문자열의 이중배열 리스트로 주어졌기 때문에 탐색속도를 고려하여 전체 set을 딕셔너리 형태로 수정한 뒤, key, value를 교차하여 저장해두었다.

def dfs(graph, start, answer, visited, city, tickets):
    print(answer)
    for i in graph[start]:
        if not visited[start][i]:
            # print(answer)
            visited[start][i] = True
            answer.append(city[i])
            dfs(graph, i, answer, visited, city, tickets)

다음은 처음에 작성한 깊이우선 탐색의 코드이다. 각각의 티켓별로 사용한 티켓의 경우 방문처리를 하고, DFS를 돌렸고, 주어진 테스트 케이스에서는 잘 통과했으나...

이렇게, 제출시에는 2개의 테스트 케이스에서 막히고 말았다..
그 이유를 살펴보니

• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

라는 제약 조건이 있었고, 이를 보고, 더이상 이동할 곳이 없는 경우에는 백트레킹으로 해당 공항을 방문 취소하고, prunning하였다.

def dfs(graph, start, answer, visited, city, tickets):
    print(answer)
    for i in graph[start]:
        if not visited[start][i]:
            # print(answer)
            visited[start][i] = True
            answer.append(city[i])
            dfs(graph, i, answer, visited, city, tickets)
            #방문할 곳을 다 돌지 못했는데, 탐색이 끝나버린 경우에는 백트래킹!
            if len(answer) < len(tickets) + 1:
                answer.pop()
                visited[start][i] = False
                print('back')

하지만... 여전히 첫번째 테스트 케이스를 통과하지 못했고, 질문하기 게시판 찬스를 사용해서 티켓이 복수로 존재할수도 있다는 것을 확인했다. 이후 visited의 T/F 배열을 해당 티켓의 수만큼 카운트해주고, 해당 티켓 사용시 -1 해주는 방식으로 코드를 수정했고,

결국 다 통과했다!!!

전체 소스 코드

def dfs(graph, start, answer, visited, city, tickets):
    for i in graph[start]:
        if visited[start][i] > 0:
            visited[start][i] -= 1
            answer.append(city[i])
            dfs(graph, i, answer, visited, city, tickets)
            if len(answer) < len(tickets) + 1:
                answer.pop()
                visited[start][i] += 1


def solution(tickets):
    answer = []
    t = set()
    for a in tickets:
        t.add(a[0])
        t.add(a[1])

    cand = list(t)
    cand.sort(key=lambda x: (x[0], x[1], x[2]))

    city = {}
    for i in range(len(cand)):
        city[cand[i]] = i
        city[i] = cand[i]

    graph = [[] for i in range(len(cand))]
    visited = [[0 for j in range(len(cand))] for i in range(len(cand))]

    for t in tickets:
        current, next = t[0], t[1]
        graph[city[current]].append(city[next])
        visited[city[current]][city[next]] += 1

    for g in graph:
        g.sort()

    start = city["ICN"]
    cnt = 1
    answer.append(city[start])
    dfs(graph, start, answer, visited, city, tickets)

    return (answer)

이후 찾아온... 다른 사람의 코드를 보고 절망할 시간..

from collections import defaultdict
def solution(tickets):
    r = defaultdict(list)
    for i,j in tickets:
        r[i].append(j)
    for i in r.keys():
        r[i].sort()

    s = ["ICN"]
    p = []
    while s:
        q = s[-1]
        if r[q] != []:
            s.append(r[q].pop(0))
        else:
            p.append(s.pop())
    return p[::-1]

defaultdict를 사용하면 내가 한 처음의 수고를 단 한번에 해결할수 있다고 한다..(절망)