Lv3. 여행경로 (DFS/BFS)

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

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

 

#1. 설계 및 풀이

 

- 처음에는 BFS로 풀다가 안된다는 걸 깨닫고 DFS로 돌렸다.

 

- DFS로 푸는데 알파벳순으로 가장 먼저 나오는 순만 생각하다가 틀렸다.

->  알파벳 순서로 DFS를 돌리는 건 맞지만,

알파벳순으로 간다고 항상 모든 항공권을 다 쓴다는 보장이 없기 때문에 모든 경우에 대해 다 돌려야 한다.

 

- 근데 리턴하는 과정에서 문제가 발생했다.

경로를 찾았다고 True를 리턴한다고 해서 바로 끝나는게 아니라

해당 함수를 호출했던 함수들도 모두 종료되어야하므로

dfs의 결과가 True이면 그 부분에서 똑같이 True를 반환해줘야 경로를 찾았을 때 바로 종료할 수 있다.

 

-> dfs를 할 때 에러가 발생하면 항상 상태 공간 트리를 생각하면서, 리턴이 잘 이루어지는지 확인하자.

 

answer = []
temp = []

def dfs(begin, tickets) :
    global answer, visited

    if 0 not in visited :
        return True
    
    candi = [] # begin에서 갈 수 있는 것 찾기
    for i in range(len(tickets)) :
        if visited[i] == 0 :
            if tickets[i][0] == begin :
                candi.append(tickets[i] + [i])
                
    candi.sort(key = lambda x : x[1]) # 알파벳 순으로 정렬
    for begin, end, idx in candi :
        visited[idx] = 1
        answer.append(end)
        if dfs(end, tickets) :
            return True #주의 !!!! 이부분도 True를 리턴해줘야 내가 원하는대로 종료
        visited[idx] = 0
        answer.pop()
            
        

def solution(tickets):
    global answer, visited, temp
    visited = [0] * len(tickets)
    answer.append("ICN")
    dfs("ICN", tickets)
    return answer