Algorithm - 프로그래머스 여행경로(DFS)

 

 

 

프로그래머스

 

 

 

오늘은 DFS 알고리즘 문제를 풀었다.

 

DFS

DFS는 깊이 우선 탐색(Depth-First Search)의 약어로,

그래프 및 트리의 한 정점에서 모든 정점을 방문하는 알고리즘 중 하나이다.

 

특징

1. 한 정점에서 시작하여 가장 깊은 곳 (최하위의 자식 노드) 까지 탐색하고, 되돌아와서 다음 가능한 경로를 탐색한다.
2. 스택(Stack) 자료구조를 사용한다.

3. 모든 정점을 방문하여야 할 때 사용된다. 
4. 정점의 이웃 정점들을 재귀적으로 방문하여 구현한다.

5. 깊이를 가늠할 수 없을 경우, 스택오버플로우가 발생할 수 있다.

 

DFS(깊이우선탐색), BFS(너비우선탐색)

 

 

 

아직 익숙치 않아서 코드를 작성하는데에 헷갈리는게 많아 어려웠다.

그래서 이번기회에 확실히 이해할 수 있도록 주석을 하나하나 달아가며 코드를 작성하였다.

 

 

import java.util.*;

class Solution {
    static boolean[] visited; // 사용한 항공권을 표시하기 위한 배열
    static ArrayList<String> allRoute; // 모든 가능한 경로를 저장하는 리스트
    
    public String[] solution(String[][] tickets) {
    String[] answer;
    visited = new boolean[tickets.length];
    allRoute = new ArrayList<>();

    // DFS 시작
    dfs("ICN", "ICN", tickets, 0);

    // 탐색을 마친 후, 알파벳 순서로 정렬
    Collections.sort(allRoute);

    // 가장 먼저 나오는 경로를 반환
    answer = allRoute.get(0).split(" ");

    return answer;
  }

  public static void dfs(String start, String route, String[][] tickets, int cnt) {
    // 모든 항공권을 사용하여 여행 경로를 구성했을 경우
    if (cnt == tickets.length) {
      // 해당 경로를 리스트에 추가
      allRoute.add(route);
      return;
    }

    // 현재 위치에서 출발하여 가능한 모든 항공권을 탐색
    for (int i = 0; i < tickets.length; i++) {
      // 아직 사용되지 않은 항공권 중 현재 위치에서 출발하는 항공권이 있을 경우
      if (start.equals(tickets[i][0]) && !visited[i]) {
        visited[i] = true; // 항공권을 사용했음을 표시
        // 다음 출발지를 도착지로 설정하여 DFS 재귀 호출
        dfs(tickets[i][1], route + " " + tickets[i][1], tickets, cnt + 1);
        visited[i] = false; // DFS를 빠져나온 후 방문 표시 해제
      }
    }
  }
}

 

 

주석을 달며 문제를 해결하니 꽤 시간이 걸렸다.

그래도 코드가 어떻게 동작하는지 자세히 알 수 있게 되어 dfs에 대해 이해할 수 있는 계기가 되었다.