[TIL] 프로그래머스 여행경로 : DFS/BFS

function solution(tickets) {
    
    // 출발지, 도착지 정보 담는 객체 생성
    const plane = {};
    
    for (const t of tickets) {
        if (!plane[t[0]]) {
            plane[t[0]] = [t[1]]; 
        } else {
            plane[t[0]].push(t[1])
        }
    }
    
    // 도착지 내림차순 정렬 .sort((a, b) => b - a); 왜 안 됨?
    for (const p in plane) plane[p].sort().reverse();
    
    // 여행 경로 정하기, 첫 출발지는 무조건 ICN
    const route = ['ICN'];
    // 출발지가 포함이기 때문에 가지고 있는 항공권보다 경로 횟수는 1회 높다
    const count = tickets.length + 1
    
    while(route.length < count){
        for (const country in plane){
            if (country === route[route.length-1] && plane[country]){
                route.push(plane[country].pop())
            }
        }
    }
    
    return route;
}

뒤늦게 이걸 풀고 있는데 지금 아니면 여유 있게 풀 수 있는 시간이 없을 거 같아서 아직 잘 모르는 것들도 풀면서 공부하려고 이제야 1주차 실습 문제들을 풀고 있다. 처음에 그래프를 통해서 풀었는데 테스트케이스 다 통과해서 당연히 될 줄 알았는데 채점하니까 케이스 4개 중에 1개밖에 통과 안 됐고 다른 건 심지어 시간 초과 됐다.

도대체 뭐 때문인가에 대해 구글링을 엄청 해봤는데 이 코드로는 예외 처리가 안 됐다.

문제의 조건 중 하나가

• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.

이거였고 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]를 입력값으로 받았을 때 ["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞서기 때문에 알파벳 순서대로 방문할 수 있도록 처리를 해줘야 한다.

그러나 다시 예외 케이스로 얘기로 돌아가보자면 위 코드로는 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ICN"]] 이걸 입력값으로 받았다면 출발지, 도착지 입력 후 알파벳 순서대로 배열 정렬을 해줬기 때문에 ICN 다음에 당연히 SFO와 ATL 중 ATL로 먼저 가게 된다. ATL에 도착하고 나면 다음 행선지로 갈 수 있는 항공권이 없기 때문에 더이상 가지 못 하고 거기에서 반복문이 종료되지 않고 계속 돌아가게 된다. 그렇기 때문에 해당 코드가 종료되지 않아 시간 초과가 발생하기 때문에 DFS를 재귀를 통해서 풀어야 한다고 한다.

참고한 블로그 링크

📝 BFS / DFS

• BFS Breadth First Search : 너비 우선 탐색

  • 큐(FIFO)를 이용하여 구현할 수 있다.
  • 시작지점에서 가까운 정점부터 순차적으로 탐색한다.
  • 예시 문제 ) 프로그래머스 : 가장 먼 노드
    이 문제는 그래프와 BFS를 이용해 풀 수 있다.

• DFS Depth First Search : 깊이 우선 탐색

  • 스택(LIFO)을 이용하여 구현할 수 있다.
  • 시작 지점에서 시작해 가장 깊은 정점까지 탐색한 후 같은 방식으로 그 다음 정점을 탐색한다.
  • 예시 문제 ) 프로그래머스 : 여행경로