[백준] 1976. 여행가자 (Java)

 

1976번: 여행 가자

 

풀이

• 다양한 방법이 있는 것 같지만 다익스트라로 풀었다.
• 우선 여행 계획에 있는 도시들은 중복될 수 있으므로 순서를 배열로 입력받음과 동시에 HashSet으로 받았다.
• HashSet에 있는 도시들만 다익스트라 알고리즘으로 경로를 갱신했다.
  • 만약 위치가 INF로 남아있으면 그 도시로는 방문이 불가능하다는 의미이다.
• 마지막으로 여행 계획에 있는 도시들을 for문으로 순회하면서 INF가 나오면 바로 "NO"를, 그렇지 않으면 "YES"를 출력하게 했다.

 

코드

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

public class Main {
    static int N, M;
    static String ans = "YES";
    static int[][] adj, dist;
    static int[] route;
    static Set<Integer> cities = new HashSet<>();
    static final int INF = 40000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        adj = new int[N + 1][N + 1];
        dist = new int[N + 1][N + 1];
        route = new int[M];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++)
                adj[i][j] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int city = Integer.parseInt(st.nextToken());
            cities.add(city);
            route[i] = city;
        }

        for (Integer city : cities) {
            Arrays.fill(dist[city], INF);
            Dijkstra(city);
        }

        for (int i = 0; i < M - 1; i++) {
            int from = route[i];
            int to = route[i + 1];

            if (dist[from][to] == INF) {
                ans = "NO";
                break;
            }
        }

        bw.write(ans);
        br.close();
        bw.close();
    }

    public static void Dijkstra(int idx) {
        dist[idx][idx] = 0;
        Queue<Integer> q = new LinkedList<>();
        q.offer(idx);

        while(!q.isEmpty()) {
            int from = q.poll();

            for (int to = 1; to <= N; to++) {
                if (adj[from][to] == 0) continue;
                if (dist[idx][from] + adj[from][to] < dist[idx][to]) {
                    dist[idx][to] = dist[idx][from] + adj[from][to];
                    q.offer(to);
                }
            }
        }
    }
}