오늘은 그래프 탐색 알고리즘에 관련된 문제를 해결하였다. 문제를 해결하면서 발생했던 이슈들과, 사고 과정들을 한번 정리해 보고자 한다.

문제

프로그래머스 코딩테스트 연습 - 여행 경로

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한 사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

해결 과정

얼핏 보니 경로를 구해야 한다고 하였다. 따라서 그래프 문제라는 것을 알 수 있었다. 그러나 일반적인 문제와는 다른 것이, 한 번 방문한 노드를 티켓이 있는 한 티켓의 수 만큼 재 방문할 수 있다는 것이다. 따라서 노드를 방문했는지 확인하는 visited 저장 공간을 HashMap으로 구성하고, graph[a].append(b), visited[a].append(true)형식으로 저장하고자 하였다.

function solution(tickets) {
  const answer = [];
  const adj = {};
  const visited = {};
  // insert
  for (const [start, end] of tickets) {
    adj[start] = start in adj ? [...adj[start], end] : [end];
    visited[start] = start in visited ? [...visited[start], false] : [false];
  }
  // ...
}

만약에 경로가 1개 이상이 존재한다면, 사전 순으로 빠른 것을 배치한다고 하였으므로, 처음 시도한 방법은 "graph에 있는 모든 요소들을 사전순으로 정렬하자!" 였다.(당연히 될줄 알고 있었음)

function solution(tickets) {
  
  // ... 위 코드에서 이어집니다.
  const routes = ["ICN"];
  // 사전순으로 배치하기
  for (const key in adj) {
    adj[key].sort();
  }
  const dfs = (node) => {
    if (!(node in adj)) return;
    adj[node].forEach((next, index) => {
      if (!visited[node][index]) {
        routes.push(next);
        visited[node][index] = true;
        dfs(next);
      }
    });
  };
  dfs("ICN");
  return routes;
}

결과는 실패. 아마도 사전순으로 방문할 경우, 모든 노드를 방문하지 못하고 완성할 수 없는 경로를 반환하는 것 같았다.

일단 dfs에서 모든 노드를 방문하여 경로를 만들 수 있으면 만들고, 경로가 1개 이상 존재할 때 사전순으로 배치하여 가장 첫번째 경로를 반환하도록 만들어야하는데, 생각나는 것이 백트래킹 형식 외에는 없었다. 백트래킹은 O(2^N)의 시간복잡도를 가지므로 크기가 1만인 현재 문제에서는 해결이 되지 못하는데, 다른 방법은 생각나지 않으므로 일단 시도해보기로 한다.

function solution(tickets) {
  const routes = ["ICN"];
  const dfs = (node, routes) => {
    if (routes.length >= tickets.length + 1) {
      answer.push([...routes]);
      return;
    }
    adj[node].forEach((next, index) => {
      if (!visited[node][index]) {
        visited[node][index] = true;
        dfs(next, [...routes, next]);
        visited[node][index] = false;
      }
    });
  };
  dfs("ICN", routes);
  answer.sort();
  console.log(answer[0]);
  return answer[0];
}

다음은 모든 노드에 대하여 방문하고, 그 경우에는 tickets.length + 1이 최종 경로가 되므로 이것을 기저사례로 하였다. 조건을 만족하면 routes의 모든 요소들을 복사하여 answer에 추가한다. routes의 모든 요소를 복사하는 이유는, 배열은 참조 객체이므로 그냥 식별자에 할당을 하게 된다면 메모리 주소가 참조되어, routes에 변화가 생기면 참조하는 모든 식별자들의 요소들도 동일하게 변하기 때문이다. dfs의 forEach부분에서 routes가 계속 변화하므로 이 방식을 취해주었다.

두번째 작성한 결과는..


이번엔 런타임에러다. 일단 런타임에러가 날 만한 곳을 찾는다. 일반적으로 배열을 순회할 때 인덱스보타 큰 값을 찾거나, 해시맵에서 키가 없는데 키 값을 찾아 배열을 돌리려고 할 경우 문제가 많이 생기므로, 그 부분을 먼저 체크해주었다. adj[node] false일 경우, 배열을 순회하지 않도록 추가로 체크해주었다.

최종 코드

function solution(tickets) {
  const answer = [];
  const adj = {};
  const visited = {};
  
  // insert
  for (const [from, to] of tickets) {
    adj[from] = from in adj ? [...adj[from], to] : [to];
    visited[from] = from in visited ? [...visited[from], false] : [false];
  }
  const routes = ["ICN"];
  const dfs = (node, routes) => {
    if (routes.length >= tickets.length + 1) {
      answer.push([...routes]);
      return;
    }
    if (!adj[node]) return;
    adj[node].forEach((next, index) => {
      if (!visited[node][index]) {
        visited[node][index] = true;
        dfs(next, [...routes, next]);
        visited[node][index] = false;
      }
    });
  };
  dfs("ICN", routes);
  answer.sort();
  console.log(answer[0]);
  return answer[0];
}

느낀 점

오늘은 그래프 알고리즘 문제를 해결해보았다. 이를 해결하면서 몇 번정도 실패 과정을 거쳤다. 일단 엣지케이스를 찾는 부분이 부족하여 첫 번째로 정답을 찾지 못하였으며, 때문에 데이터 입력값의 여러 경우를 생각하지 못하여 예외처리를 잘못했기 때문에 두 번째 시도에서 에러가 발생하였다. 문제에서 주어진 테스트케이스를 맞췄다고 바로 테스트를 해보는 것이 아닌, 여러가지 극한 경우를 생각하면서 이 경우에도 되는지 한번 테스트하고, 이해가 잘 안되면 손으로 구현하는 연습을 꾸준히 해야겠다.