(JAVA) [BOJ]백준 9205번, 맥주 마시면서 걸어가기

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

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

 

9205, 맥주 마시면서 걸어가기

📌 [ 난이도 : 골드 5 ]

난이도가 올라갈수록 문제를 이해하는데 걸리는 시간이 오래 걸리는 것 같다. 정리하자면 N+2 개 줄에 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 각각 주어지는데 50M 가기 전에 맥주 한병을 마셔야 하고 맥주 한 박스에는 맥주 20개가 들어있기 때문에 좌표간의 거리가 1000M (50M당 맥주 1개, 20개 보유) 면 갈 수 있다는 의미이다.

 

그렇기 때문에 각 좌표끼리 연결되어 있는 지 확인하고 그 좌표가 이어져 최종 목적지까지 가는지 확인하면 되는 문제이다.

 

📚 Process

초기화 및 선언

: 테스트 케이스 횟수 T를 입력받고 그만큼 해당 로직을 반복한다. N 을 입력받고 N+2 만큼의 각 좌표들을

ArrayList<int[]> a 에 넣어준다. 이는 x좌표와 y좌표를 의미한다.

또한 각 좌표들끼리 이동할 수 있는지 여부를 확인할 boolean[] isSearch 를 생성해준다.

 

 

탐색

: 0 - N+2 까지의 정점을 모두 순회하며 1,000m 이하를 만족하면 두 정점을 연결시켜준다.(양방향으로)

for(int i=0; i<N+2; i++) {
    for(int j=i+1; j<N+2; j++) {
        if(isConnected(a.get(i), a.get(j))) {
            isSearch[i][j] = isSearch[j][i] = true;
        }
    }
}

모든 탐색이 끝났으면 Floyd Warshall 알고리즘을 통해 각 정점들을 통해 연결되어 있는지 확인한다.

Floyd Warshall 이란 모든 최단 경로를 구하는 알고리즘이다. 다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이라면, 여기서 사용한 Floyd Warshall 은 모든 노드 간 연결 여부를 구하는 의도이다.

public static void fload() {
    for(int k = 0; k < N + 2; k++) {
        for(int i = 0; i < N + 2; i++) {
            for(int j = 0; j < N + 2; j++) {
                if(isSearch[i][k] && isSearch[k][j]) {
                    isSearch[i][j] = true;
                }
            }
        }
    }
}

이러한 과정을 통해 isSearch[i][k] 와 isSearch[k][j] 가 모두 true 즉, 연결되어 있다면 i->k->j 도 연결될 수 있다는 의미이다.

 

✅ 전체 코드

: 더 자세한 설명들은 주석으로 달아두었다.

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;
    static int T,N;
    static ArrayList<int[]> a;
    static boolean[][] isSearch;
    
    public static void main(String[] args) throws IOException {
        T = Integer.parseInt(br.readLine());

        while(T-->0) {
            input();
            pro();
        }
        
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    public static void input() throws IOException {
        N = Integer.parseInt(br.readLine());

        // 집,편의점,페스티벌 위치를 저장
        a = new ArrayList<>();

        int x,y;
        for(int i=0; i<N+2; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            a.add(new int[]{x,y});
        }

        isSearch = new boolean[N+2][N+2];
    }

    public static void pro() {
        /**
         * 맨해튼 거리 1,000m 이하를 만족하는 두 정점을 찾음
         * 그 두 거리는 서로 연결되어 있다고 판단하고 경로 배열에 true 
         */
        for(int i=0; i<N+2; i++) {
            for(int j=i+1; j<N+2; j++) {
                if(isConnected(a.get(i), a.get(j))) {
                    isSearch[i][j] = isSearch[j][i] = true;
                }
            }
        }

        fload();

        // 0->N+1 은 연결되어 있는 지 확인
        sb.append((isSearch[0][N+1] ? "happy" : "sad") + "\n");
    }

    // 50m, 20병이기 때문에 거리제한은 1,000m
    public static boolean isConnected(int[] p1, int[] p2) {
        return Math.abs(p1[0]-p2[0]) + Math.abs(p1[1]-p2[1]) <= 1000;
    }

    /**
     * 플로이드 와샬 알고리즘
     * [i][k] && [k][j] 이면 i->k->j 는 연결되어있다!
    */
    public static void fload() {
        for(int k = 0; k < N + 2; k++) {
            for(int i = 0; i < N + 2; i++) {
                for(int j = 0; j < N + 2; j++) {
                    if(isSearch[i][k] && isSearch[k][j]) {
                        isSearch[i][j] = true;
                    }
                }
            }
        }
    }
}