Floyd-Warshall

특징

• 다익스트라 알고리즘과는 달리 모든 노드 쌍에 대해 최단 거리를 구함

• 음의 가중치를 가지는 그래프에서도 쓸 수 있음

• 3중 for문

• (출발지-도착지)의 최단경로 값이 빠른지, (출발지-경유지)+(경유지-도착지)의 최단경로 값이 빠른지 비교하는 알고리즘

문제

키 순서

package org.example;

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

public class Main {
    private static StringBuilder sb = new StringBuilder();
    private static int N, M;
    private static int[][] arr;

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N + 1][N + 1];

        // 무한대 입력
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= N; j++) {
                arr[i][j] = 999999999;
            }
        }

        // 입력
        for (int m = 0; m < M; m++) {
            st = new StringTokenizer(br.readLine());

            arr[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = 1;
        }

        for (int mid = 1; mid <= N; mid++) { // 가운데 노드
            for (int start = 1; start <= N; start++) { // 시작 노드
                for (int end = 1; end <= N; end++) { // 끝 노드
                    // 시작 ~ 마지막 > 시작 ~ 가운데 + 가운데 + 끝 -> 갱신
                    if (arr[start][end] > arr[start][mid] + arr[mid][end]) {
                        arr[start][end] = arr[start][mid] + arr[mid][end];
                    }
                }
            }
        }

        int answer = 0;

        for (int i = 1; i <= N; i++) {
            int count = 0;

            for (int j = 1; j <= N; j++) {
                if (arr[i][j] != 999999999 || arr[j][i] != 999999999) {
                    count += 1;
                }
            }

            if (count == N - 1) {
                answer += 1;
            }
        }

        System.out.println(answer);
    }
}

맥주 마시면서 걸어가기

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

public class Main {
    private static StringBuilder sb = new StringBuilder();
    private static int N;
    private static int[][] distance;
    private static Point[] points;
    private static final int INF = 327670;

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

        int T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            N = Integer.parseInt(br.readLine());
            points = new Point[N + 2];
            for(int i = 0; i < N + 2; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                points[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            }

            distance = new int[N + 2][N + 2];
            for (int i = 0; i < N + 1; i++) {
                for(int j = i + 1; j < N + 2; j++) {
                    distance[i][j] = distance[j][i] = INF;

                    // 거리 측정
                    int diff = Math.abs(points[i].y - points[j].y) + Math.abs(points[i].x - points[j].x);

                    // 거리가 50 * 20 이하이면 갈 수 있는 길이다.
                    if (diff <= 50 * 20) {
                        distance[i][j] = distance[j][i] = 1;
                    }
                }
            }

            for (int k = 0; k < N + 2; k++) {
                for (int i = 0; i < N + 2; i++) {
                    for (int j = 0; j < N + 2; j++) {
                        distance[i][j] = Math.min(distance[i][j], distance[i][k] + distance[k][j]);
                    }
                }
            }

            if (0 < distance[0][N + 1] && distance[0][N + 1] < INF) {
                System.out.println("happy");
            }
            else {
                System.out.println("sad");
            }
        }
    }
}