[프로그래머스] DFS/BFS - 여행경로, Python

다음은 프로그래머스의 DFS/BFS 문제 중 여행경로 문제입니다.

 

 

 

입출력 예시는 다음과 같습니다.

 

두번째 예시는 알파벳 순서의 조건으로 해당 결과가 반환된 것입니다.

 

 

저는 다음과 같이 생각의 흐름을 잡았던 것 같습니다.

 

1. 배열을 그대로 사용하기보다는 dictionary의 형태로 그래프를 만들어서 사용하자!

- 저는 초반에 defaultdict(set)으로 구현했다가 list로 바꿔주었는데 set으로 사용하시면 똑같은 티켓이 있는 경우에 하나의 티켓처럼 사용되어서 set으로 구현했습니다.  

 

2. 알파벳 순서가 중요하다면 ticket들을 알파벳순으로 정렬해서 dictionary를 만들면 되지 않을까?

- dictionary는 넣는 순서대로 들어간다. 여러 경우를 찾는 게 싫어서 정렬해서 넣었는데 이 생각하는데 좀 걸렸네요...

 

3. ticket들은 알파벳 순으로 정렬되어 있으니 그대로 꺼내서 for문을 사용하는 형식으로 DFS를 사용하자!

 

-끝- 

 

 

CODE

from collections import defaultdict
from copy import deepcopy

def solution(tickets):
    length = len(tickets) + 1
    answer = [0] * length
    sticket = sorted(tickets, key=lambda k: (k[0], k[1]))

    mydict = defaultdict(list)
    # Make Dictionary
    for i, j in sticket:
        mydict[i].append(j)

    # DFS
    def dfs(node, mdict, depth, ans):
    	# 완성된 경로를 찾았을 경우
        if(depth == length):
            ans[-1] = node
            return ans
        ans[depth-1] = node
        
        # 다음 티켓이 없는 경우
        line = mdict[node]
        if(len(line) == 0) : return False
        
        # 현재 가능한 다음 티켓들에 대해 반복
        for i in line:
            temp = deepcopy(mdict)
            temp[node].remove(i)		# 현재 노드 제거
            res = dfs(i, temp, depth+1, ans)	# 재귀
            if not (res == False) : return ans
        return False				# 요주의 문장...

    return dfs('ICN', mydict, 1, answer)

 

저는 이 문제를 풀면서 저 요주의 문장에서 재귀의 개념이 아직 많이 부족하구나 싶었습니다...ㅠㅠ

return False 문장이 없는 상태로 간단한 케이스들을 모두 통과했는데 실행해보면 테스트 케이스 1번에서 틀리더라고요ㅠㅠ

똑같은 티켓이 있는 경우도 모두 문제없다고 생각했고 간단한 테스트 케이스들 마저도 통과했었는데 말이죠ㅠㅠ

 

정말 한두 시간은 헤매다 보니 왼쪽의 그래프의 경우에서 틀린다는 걸 알았습니다...

1. ICN에서 B를 선택

2. B에서 D를 선택

3. D에서 완료 조건(depth) 충족하지 못하여 return False

4. B에서 for문이 완료, B단계 종료(반환이 없음)

 

ICN에서 B의 반환으로 res이 None 되어서 if문장을 충족하고 return ans문장이 실행돼버리더라고요..

 

후에 for문이 끝나고 원하는 경로가 없는 경우에 돌아오는 것이 깊은 단계에서 어려워지는 거였어요.

그리고 요주의 문장을 넣고 나니 통과하더라고요.

 

여기서 DFS/BFS공부를 더 꼼꼼히 해야 된다는 생각을 하게 되었네요ㅎㅎ

 

부족한 점이 많은 글이지만 봐주셔서 감사합니다 :)

잘못된 점이 있다면 댓글 남겨주시면 감사하겠습니다 :)