[백준]9250번 맥주 마시면서 걸어가기 - Java

문제

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

9205번: 맥주 마시면서 걸어가기

 

 

풀이

플로이드 와샬 문제이다!

최근에 배웠음.

처음 설명을 들을 때는 되게 쉽네~ 라고 생각했지만 막상 문제를 풀어보니까 잘 모르겠더라 ㅎㅎㅎ

 

다익스트라가 한 정점에서 모든 정점으로의 최소 비용 거리를 구하는 알고리즘이라면,

플로이드 와샬은 모든 정점에서 모든 정점으로의 최소 비용 거리를 알 수 있음!!

다만 3중 for문을 돌기 때문에 크기가 크면 터질 수도 있으니까 조심하자!!!

 

경유지가 가장 바깥쪽의 for문으로 들어가야됨! 이게 중요. 헷갈리지 마셈 ㅎ

 

자세한건 주석으로!

 

 

코드

// 9205번 맥주 마시면서 걸어가기
// https://www.acmicpc.net/problem/9205

package BAEKJOON;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Num9205_맥주마시면서걸어가기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 수

        for (int t = 0; t < T; t++) {
            int n = Integer.parseInt(br.readLine());
            int[][] distance = new int[n + 2][n + 2];
            boolean[][] check = new boolean[n + 2][n + 2];
            List<int[]> list = new ArrayList<>();
            for (int i = 0; i <= n + 1; i++) { // 입력
                st = new StringTokenizer(br.readLine());
                list.add(new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())});
            }


            for (int i = 0; i <= n + 1; i++) {
                for (int j = 0; j <= n + 1; j++) {
                    int[] p1 = list.get(i), p2 = list.get(j);
                    // 거리 계산
                    distance[i][j] = Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);

                    // 편의점을 가기 전까지 맥주가 떨어지지 않으면 가는 것이 가능!
                    if (distance[i][j] <= 50 * 20) {
                        check[i][j] = true;
                    }
                }
            }


            for (int k = 0; k <= n + 1; k++) { // 경유지(편의점)
                for (int i = 0; i <= n + 1; i++) {
                    for (int j = 0; j <= n + 1; j++) {
                        // i에서 k로 가는 것이 가능하고, k에서 j로 가는 것이 가능하다면
                        // i에서 j로 가는 것이 가능!
                        if (check[i][k] & check[k][j]) {
                            check[i][j] = true;
                        }
                    }
                }
            }

            // 집에서 페스티벌까지 맥주가 떨어지지 않고 갈 수 있으면
            if (check[0][n + 1]) {
                System.out.println("happy");
            } else {
                System.out.println("sad");
            }
        }
    }
}