[Programmers Lv.3 | JS] 여행경로

Bori·2023년 5월 4일

Algorithm

목록 보기

20/26

처음 풀이

const bfs = (tickets, start) => {
    const queue = [];
    const visited = []; // (1)
    const travelRoute = [];

    queue.push(start);
    
    while(queue.length !== 0) {
        const airport = queue.shift();
        
        for(const ticket of tickets) {
            if (!visited.includes(ticket) && airport === ticket[0]) {
                visited.push(ticket);
                queue.push(ticket[1]);
                break; // (2)
            }
        }
        
        travelRoute.push(airport);
    }
    
    return travelRoute;
}

function solution(tickets) {
  // 항상 "ICN" 공항에서 출발
  const start = "ICN"

  // 만약 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return
  tickets.sort();
  
  return bfs(tickets, start);
}

이 풀이에서 놓친 부분

동일한 티켓이 여러 개인 경우 고려하지 않음 - (1)
알파벳 순서가 앞서는 티켓만 고려 - (2)
- 알파벳 순서만 고려한 경우 모든 도시를 방문할 수 없는 경우가 있다.
  (제한사항 : 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.)
- 따라서, 다른 경로를 고려하지 않음

⇒ 테스트 케이스 1, 2번 실패함

나의 풀이

function solution(tickets) {
    const start = "ICN"
    const travelRoute = [];
    const visited = Array.from({length: tickets.length}, _ => false);
    
    // 알파벳 순서로 티켓 정렬
    tickets.sort();
    
    const dfs = (path, index) => {
        const airport = path[path.length - 1];
        
        // 모든 도시를 방문했을 경우 여행경로 생성
        if(index === tickets.length) travelRoute.push(...path); 
        // 이미 여행 경로가 생성되었을 경우 이후 다른 여행경로를 생성하지 않기 위해 종료
        // 정렬한 상태이므로 다른 여행경로를 고려할 필요가 없다.
        if (travelRoute.length) return; // (4)
        
        // 항공권 순회
        tickets.forEach((ticket, idx) => {
            const [departure, arrive] = ticket;

            // 방문 여부, 다음 항공권 출발지 확인
            if (!visited[idx] && departure === airport) {
                visited[idx] = true;
                dfs([...path, arrive], index + 1);
                // 모든 도시를 방문할 수 없는 경우, 방문처리 하지 않고 다음 항공권을 확인
                visited[idx] = false; // (3)
            }
        })
    }
    
    dfs([start], 0);
    
    return travelRoute;
}

문제를 풀면서

DFS(Depth-First Search)

깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
stack, 재귀함수 이용
탐색 수행 시 O(n)의 시간 복잡도
노드 탐색 순서
- 루트 노드를 stack에 넣고 방문 처리 한다.
- stack의 최상단 노드의 인접 노드 확인한다.
  - 방문하지 않은 인접 노드가 있다면, 그 인접 노드를 stack에 넣고 방문 처리한다.
  - 방문하지 않은 인접 노드가 없다면, stack에서 최상단 노드 꺼낸다.
- 두 번째 과정을 더 이상 수행할 수 없을 때까지 반복한다.
예제

const dfs = (graph, v, visited) => {
  //1. 탐색 시작 노드 방문 처리
  visited[v] = true;
  console.log(v);
  
  //2. 탐색 노드의 인접 노드 확인 
  for(const cur of graph[v]){
    if(!visited[cur]){
      dfs(graph, cur, visited);
    }
  }
}

let graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7],
]

let visited = [...Array(9).fill(false)];

dfs(graph, 1, visited);

다른 풀이를 보면서

이 문제는 최단 여행경로를 구하는 문제가 아니므로 bfs보다는 dfs로 접근하여 모든 항공권을 순회해야 한다.
다른 분들의 풀이를 참고하면서 풀이과정을 따라가는데 (3), (4) 코드를 이해하는데 오래걸렸다.

(3) 코드

알파벳 순서대로 항공권을 순회하지만, 모든 도시를 방문할 수 없는 경우가 있다.
문제의 제한 사항에서 모든 도시를 방문할 수 있어야 했기 때문에, 현재 도착지와 다음 항공권의 출발지가 같더라도 방문처리 하지 않고 다른 항공권을 확인해야했다.
이를 통해 모든 도시를 방문할 수 있는 모든 여행 경로를 생성할 수 있어야 한다.