[프로그래머스] DFS/BFS 4. 여행경로

문제

https://programmers.co.kr/learn/courses/30/parts/12421

프로그래머스

 

---

풀이

 

카카오 문제를 풀다보니, 구현력을 요구하는 문제가 생각보다 많았다.

내가 생각하기에 깔끔한 풀이가 아니더라도 그걸 끝까지 구현해 내는 것이 관건인 문제들이 많았다.

DFS/BFS 카테고리에 있었지만 DFS/BFS 의 풀이는 생각나지 않았고 다른 풀이가 떠올랐는데, 정답이 아닐 것 같다고 생각했지만 일단 구현해보기로 했다.

 

처음에는 단순하게 알파벳순으로 정렬하여 출발지점에서 도착할 수 있는 곳들 중 알파벳이 빠른 순서대로 방문하였다.

그런데 1,2번 테스트케이스에서 오류가 발생했다.

 

입력값 〉	[["ICN", "COO"], ["COO", "ICN"], ["ICN", "BOO"]]
기댓값 〉	["ICN", "COO", "ICN", "BOO"]

와 같은 상황에서 모두 방문하지 않았는데 ICN BOO 를 선택하고 끝나버렸다.

그래서 나름 끝까지 해보겠다고 끝지점을 찾아 우선순위에서 제외하려고 했다.

끝지점은 제일 마지막에 도착하는 공항으로 전체 입력값에서 ICN을 제외하고 유일하게 홀수번 입력될 것이므로

그걸 기준으로 찾으려 했다.

from collections import Counter

def solution(tickets):
    answer = []
    
    dic = {}
    for t in tickets:
        if t[0] not in dic:
            dic[t[0]] = 1
        else:
            dic[t[0]] += 1
        if t[1] not in dic:
            dic[t[1]] = 1
        else:
            dic[t[1]] += 1
    
    print(dic)
    
    for d in dic:
        if dic[d] % 2 != 0 and d != "ICN":
            dest = d
            break
    
    print(dest)
    
    def destNum(starts):
        num = 0
        for s in starts:
            if s[1] == dest:
                num += 1
        return num
    
    def f(start):
        if not tickets:
            return
        
        starts = [t for t in tickets if t[0] == start]
        if destNum(tickets) == 1:
            for s in starts:
                if s[1] == dest:
                    starts.remove(s)
                    break
        minAirport = min(starts)
        answer.append(minAirport[1])
        tickets.remove(minAirport)
        f(minAirport[1])
        
    answer.append("ICN")
    f("ICN")
    
    
    return answer

그런데 코드가 너무 길어지는데다가 이 풀이가 맞겠다는 확신도 없어서 관뒀따..

 

블로그를 찾아보니 DFS문제라고 했다.

근데 그거 보고 나서도 왜 이 문제가 DFS문제인건지 완전히 이해가 안갔었다.

그래서 다른사람 코드 다 뜯어보고 예시 찍어보면서 왜 이 풀이가 나왔는지 이해해봤다

 

def solution(tickets):
    # 1. 그래프 생성
    routes = dict()

    for (start, end) in tickets:
        routes[start] = routes.get(start, []) + [end]  

    # 2. 시작점 - [끝점] 역순으로 정렬    
    for r in routes.keys():
        routes[r].sort(reverse=True)

    # 3. DFS 알고리즘으로 path를 만들어줌.
    st = ["ICN"]
    path = []
    
    while st:
        top = st[-1]

        if top not in routes or len(routes[top]) == 0:
            path.append(st.pop())
        else:
            st.append(routes[top][-1])
            routes[top] = routes[top][:-1]
    
    # 4. 만든 path를 거꾸로 돌림.
    answer = path[::-1]
    return answer

출처) https://gurumee92.tistory.com/165

 

 각 지점을 모두 순회해야 하는 "완전 탐색"이 필요한 경우, 대체로 DFS 알고리즘을 사용하면 문제를 쉽게 풀 수 있습니다. 

 

위 예시의 ICN -> BOO처럼 경로가 끊기는 경우 BOO를 정답 리스트에 넣고 스텍에서 BOO의 출발지 ICN을 기준으로 다른 경로를 탐색한다.

그렇게 모든 경로를 탐색하게 된다. 아래 사진 참고

 

내가 DFS/BFS에서 약한건지 직관적으로 이해하기 어려웠다... 더 많이 풀어봐야겠다.

 

이미 남의코드를 다 뜯어봐서 의미는 없지만,, 직접 해봤다

from collections import Counter

def solution(tickets):
    tickets.sort(reverse=True)
    
    dic = {}
    for t in tickets:
        if t[0] in dic:
            dic[t[0]].append(t[1])
        else:
            dic[t[0]] = [t[1]]
    
    stack = ["ICN"]
    answer = []

    while stack:
        top = stack[-1]
        if top not in dic or len(dic[top]) == 0:
            answer.append(stack.pop())
        else:
            stack.append(dic[top].pop())
    
    return list(reversed(answer))