[JUNGOL/Java] 2097. 지하철

[JUNGOL/Java] 2097. 지하철

JUNGOL

---

문제 해석

이 문제는 주어진 도시의 지하철 경로 중 특정한 도시에서 목적지 도시까지 가는 최소 비용 경로를 찾는 것이다. 이를 위해 주어진 인접 행렬을 이용하여 그래프의 최단 경로를 찾는 알고리즘이 요구된다.

풀이 과정

제출한 코드는 DFS(깊이 우선 탐색)를 이용하여 가능한 모든 경로를 탐색하고, 그 중에서 최소 비용을 갖는 경로를 찾아내는 접근 방식을 사용하고 있다. dfs 함수는 현재 노드 인덱스와 방문한 노드들을 표시하는 비트 마스크를 인자로 받으며, 모든 가능한 경로를 재귀적으로 탐색한다.

 

• graph: 각 도시간 이동 비용이 저장된 2차원 배열
• dfs 함수: 현재 노드와 방문한 노드들의 상태를 나타내는 비트 마스크를 이용하여 모든 경로를 탐색
• sel: 현재까지 선택된 경로에 포함된 노드들의 리스트
• ans: 최소 비용을 저장하는 변수, 이는 시작할 때 최대 정수값으로 초기화되어 각 경로의 비용을 계산하여 최소값을 갱신한다.

 

각 노드에서 다른 모든 노드로 이동 가능성을 체크하면서, 이미 방문한 노드를 제외하고 탐색을 진행한다. 이 때, 비트 마스크를 이용하여 각 노드의 방문 여부를 효율적으로 관리한다.

코드

package edu.ssafy.im.JUNGOL.Gold.G5.No2097;

import java.io.*;
import java.util.*;

public class Main {
    private int[][] graph; // 도시 간 이동 비용을 저장하는 2차원 배열
    private int m; // 목적지 도시의 인덱스
    private int ans = Integer.MAX_VALUE; // 최소 비용을 저장할 변수, 초기값은 매우 큰 수
    private List<Integer> sel = new ArrayList<>(); // 선택된 경로를 저장하는 리스트

    public static void main(String[] args) throws IOException {
        new Main().sol(); // 문제를 해결하는 메인 로직 실행
    }

    private void sol() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken()); // 도시의 수
        m = Integer.parseInt(st.nextToken()); // 목적지 도시 인덱스

        graph = new int[n][n]; // 도시간 이동 비용을 저장할 배열 초기화
        for (int i = 0; i < graph.length; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < graph.length; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken()); // 비용 입력 받기
            }
        }

        dfs(0, 0); // DFS를 시작, 시작 노드는 0, 방문한 노드 없음
        sb.append(ans); // 최소 비용 결과를 StringBuilder에 추가
        bw.write(sb.toString()); // 결과 출력
        bw.flush();
        bw.close();
    }

    private void dfs(int i, int v) {
        if(i == m) { // 목적지에 도달한 경우
            int sum = 0;
            for(int s: sel) { // 현재까지 선택된 경로의 비용을 합산
                sum += s;
            }
            ans = Math.min(ans, sum); // 최소 비용 갱신
            return;
        }

        for (int j = 0; j < graph.length; j++) { // 모든 도시에 대해
            if((v & (1 << j)) == 0 && i != j) { // 아직 방문하지 않은 도시이고 자기 자신이 아니면
                System.out.println(sel.toString()); // 디버깅을 위한 현재 경로 출력
                sel.add(j); // 경로에 도시 추가
                dfs(i+1, v | 1 << j); // 다음 노드 방문
            }
        }
    }
}

시간 복잡도 분석

이 알고리즘은 DFS를 사용하여 모든 가능한 경로를 탐색하므로, 시간 복잡도는 O(n!)이다. 각 노드에서 모든 다른 노드로의 가능한 경로를 탐색하기 때문에, 노드의 수가 증가함에 따라 계산 시간이 기하급수적으로 증가한다.

느낀점

이 문제를 통해 DFS를 사용하여 모든 가능한 경로를 탐색하는 방식과 비트 마스크를 활용한 방문 관리 방법을 학습할 수 있었다. 다만, 최적화된 알고리즘을 사용하지 않아 큰 입력에서는 성능 저하가 예상된다. 이를 개선하기 위해 다익스트라 알고리즘 같은 최단 경로 알고리즘을 적용할 필요가 있다.