자료구조/문제풀이

[백준 JAVA] 17396 백도어

휴먼코딩 2024. 9. 10. 18:49

17396 백도어

https://www.acmicpc.net/problem/17396

문제설명

그래프의 각 노드는 시야에 있는지 여부에 따라 통과할 수 있는지 결정되며, 목표 노드는 시야에 관계없이 통과할 수 있다.

주어진 그래프의 엣지와 노드의 시야 상태를 바탕으로 시작 노드(0번 노드)에서 목표 노드(n-1)까지의 최단 경로를 구한다.

 

 

접근방식

우선순위 큐(PriorityQueue)를 사용할 때의 시간복잡도

  • 노드 삽입 및 추출: O(log ⁡n)
  • 엣지 완화: 각 엣지에 대해 큐에 삽입하거나 거리 업데이트를 수행하므로 총 O(m log⁡ n)이다.

따라서, 전체 시간 복잡도는 O((n+m)log⁡n)

 

문제 조건 분석 과정

다익스트라 알고리즘을 사용해 최단거리를 찾는다.

추가적으로, 노드가 시야에 있는지 여부에 따라 경로 선택에 제약이 있다. 

  1. 그래프 표현:
    • 그래프는 인접 리스트 형태로 저장한다. 각 노드는 그 노드와 연결된 다른 노드들과의 엣지 정보를 가지고 있다.
  2. 시야 제약:
    • 각 노드가 시야에 있는지 여부를 배열로 저장한다. 시야에 있는 노드는 통과할 수 있지만, 시야에 없는 노드는 기본적으로 통과할 수 없다. 단, 목표 노드(n-1)는 예외로 시야에 없어도 통과할 수 있다.
  3. 다익스트라 알고리즘:
    • 우선순위 큐를 사용하여 최단 거리 우선으로 노드를 처리한다.
    • 시작 노드부터 시작하여 인접 노드를 방문하면서 최단 거리 업데이트를 수행한다.
    • 시야에 없는 노드는 거치지 않고, 목표 노드는 예외로 처리하여 통과할 수 있도록 한다.

전체코드

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

public class Main_17396백도어 {

    // 노드와 엣지의 수
    static int n, m;
    // 각 노드가 시야에 있는지 여부를 저장하는 배열
    static boolean[] sight;
    // 그래프를 표현하는 인접 리스트 (각 노드는 이웃 노드들의 리스트를 가짐)
    static ArrayList<Node>[] list;
    // 시작 노드(0번 노드)부터 각 노드까지의 최단 거리를 저장하는 배열
    static long[] dist;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 노드와 엣지의 수를 파싱
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        // 각 노드가 시야에 있는지 여부를 저장하기 위한 배열 초기화
        sight = new boolean[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int flag = Integer.parseInt(st.nextToken());
            sight[i] = (flag == 1); // 플래그가 1인 노드는 시야에 있음
        }

        // 인접 리스트 초기화
        list = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            list[i] = new ArrayList<>();
        }

        // 그래프의 엣지 정보를 읽어옴
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken()); // 시작 노드
            int e = Integer.parseInt(st.nextToken()); // 끝 노드
            int c = Integer.parseInt(st.nextToken()); // 엣지의 비용
            // 엣지를 인접 리스트에 추가 (양방향)
            list[s].add(new Node(e, c));
            list[e].add(new Node(s, c));
        }

        br.close(); // BufferedReader 닫기

        // 거리 배열을 무한대로 초기화 (Long.MAX_VALUE)
        dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[0] = 0; // 시작 노드(0번 노드)의 거리는 0

        // 다익스트라 알고리즘을 실행하여 최단 경로를 찾음
        dijkstra();

        // 목표 노드(n-1)까지의 최단 거리를 출력
        // 거리가 여전히 무한대이면 노드에 도달할 수 없다는 의미이므로 -1 출력
        if (dist[n - 1] == Long.MAX_VALUE) System.out.println("-1");
        else System.out.println(dist[n - 1]);
    }

    public static void dijkstra() {
        // 최단 거리 노드를 우선적으로 처리하기 위한 PriorityQueue
        PriorityQueue<Node> q = new PriorityQueue<>();
        // 방문한 노드를 추적하기 위한 배열
        boolean[] visited = new boolean[n];
        // 거리 0으로 시작 노드(0번 노드)를 큐에 추가
        q.offer(new Node(0, 0));

        // 노드 처리
        while (!q.isEmpty()) {
            Node current = q.poll(); // 최단 거리를 가진 노드 추출

            // 이미 방문한 노드이면 건너뜀
            if (visited[current.node]) continue;
            visited[current.node] = true;

            // 엣지 완화
            for (Node next : list[current.node]) {
                // 시야에 없는 노드는 건너뛰되, 목표 노드는 예외
                if (next.node != n - 1 && sight[next.node]) continue;
                // 새로운 경로가 더 짧은 경우 거리 업데이트
                if (dist[next.node] > dist[current.node] + next.cost) {
                    dist[next.node] = dist[current.node] + next.cost;
                    // 새로운 경로를 큐에 추가
                    q.offer(new Node(next.node, dist[next.node]));
                }
            }
        }
    }

    public static class Node implements Comparable<Node> {
        int node; // 노드 인덱스
        long cost; // 이 노드까지의 비용

        // 생성자
        public Node(int node, long cost) {
            this.node = node;
            this.cost = cost;
        }

        // 우선순위 큐에서 노드 간 비교 (비용이 작은 노드가 우선)
        @Override
        public int compareTo(Node n) {
            return Long.compare(this.cost, n.cost);
        }
    }
}