[프로그래머스] 여행경로 - Python (DFS)

링크: https://school.programmers.co.kr/learn/courses/30/lessons/43164

프로그래머스

아이디어

• dfs bfs 뭘 사용해도 될 듯?
• dfs를 이용해서 풀어보자 (재귀)
• ICN부터 dfs탐색 시작
• 알파벳 순 판별은 대소비교를 통해 진행
• 지나간 경로는 del

구현(실패)

def solution(tickets):
    # 경로를 저장할 배열
    global road
    road = ["ICN"]
    # ICN부터 시작
    dfs("ICN", tickets)
    return road

# dfs 함수
def dfs(x, tickets):

    # 배열이 비었으면 끝
    if len(tickets) == 0:
        return

    tmp_i = 0
    tmp = 'ZZZZ'
    for i in range(len(tickets)):
    	# 갈 수 있는 경로인지와 알파벳 우선순위 판별
        if tickets[i][0] == x and tickets[i][1] < tmp:
            tmp = tickets[i][1]
            tmp_i = i
    road.append(tmp)
    del tickets[tmp_i]
    # 재귀 호출
    dfs(tmp, tickets)

\

• 2개의 테스트 케이스가 실패가 나온다
• 시간적 여유는 많아 보이니 어느 부분에서 예외가 발생하는지 찾아보자

틀린 원인 찾기

• 무조건 알파벳 순으로 우선순위인 것을 쓰면 안 되는 경우가 있다
• [["ICN", "BOO"], ["ICN", "COO"], ["COO", "DOO"], ["DOO", "COO"], ["BOO", "DOO"], ["DOO", "BOO"], ["BOO", "ICN"], ["COO", "BOO"]]
• 위의 입력을 받은 경우 알파벳 우선순위만 가져와 경로를 짜면 막다른 길에 도달하게 된다.
• 이 경우 단순 재귀만 사용할게 아니라 스택의 성질로 막다른 길이면 다시 되돌아가 탐색을 진행하게 코드를 수정해야 할 듯하다.

아이디어_2

• 위의 원인을 해결하기 위해선 방문처리를 del이 아닌 방문 배열을 따로 만들어 관리해야 할 듯하다.
• 몇 번째 경로인지 숫자를 방문 경로에 저장하고 탐색 중 막다른 길에 오면 그 인댁스 방문처리 배열의 요소를 다시 -1로 만들어 막아두고 최근 경로를 가지고 dfs 
• 다른 경로를 찾으면 -1인 경로 다시 0으로 열어주기

구현(성공)

def solution(tickets):

    # 경로와 방문처리를 저장할 배열
    global road, check
    road = ["ICN"]
    check = [0]*len(tickets)

    # ICN부터 시작
    dfs("ICN", tickets)

    return road

def dfs(x, tickets):
    # 경로가 완성됐으면 끝
    if len(road) == len(tickets)+1:
        return

    tmp_i = 0
    tmp = 'ZZZZ'
    for i in range(len(tickets)):
        if check[i] == 0 and tickets[i][0] == x and tickets[i][1] < tmp:
            tmp = tickets[i][1]
            tmp_i = i

    # 다른 길을 찾았으면 막다른 길 다시 열어주기
    for i in range(len(check)):
        if check[i] == -1:
            check[i] = 0

    # 막다른 길이면 -1로 표시해서 막다른 길이라고 표시
    if tmp == 'ZZZZ':
        no = road.pop()
        check[check.index(max(check))] = -1
        dfs(road[-1],tickets)
    else:
        road.append(tmp)
        check[tmp_i] = len(road)-1
        dfs(tmp, tickets)

대박... 맞았다...! 😎

마무리

• 진짜 성공했을 때 희열감 너무 조아.. ㅋㅋㅋㅋ
• 내가 한 방식은 뭔가 dfs의 재귀와 스택의 짬뽕인 것 같음
• 분명 더 좋은 코드가 있을 것 같지만 나름 만족한다.
• dfs 이젠 다 풀 수 있을 것 같은 자신감 ㅋㅎ