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

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

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

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

class Point{
    int x;
    int y;

    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}
public class Main {

    //맨헤튼 거리 안에 갈 수 있는 정점을 연결해준다, 맥주 20개 * 50m = 1000m
    static ArrayList<Point> arr;
    static ArrayList<ArrayList<Integer>> graph;
    static Queue<Integer> queue;
    static boolean[] visited;
    static int n, t;

    static boolean bfs(int x, int n){
        queue.add(x);
        visited[x]=true;

        while(!queue.isEmpty()){
            int now = queue.poll();

            if(now==n+1) return true;


            for(int nxt : graph.get(now)){
                if(!visited[nxt]){
                    visited[nxt]=true;
                    queue.add(nxt);
                }
            }

        }
        return false;

    }
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        t = Integer.parseInt(br.readLine()); //tc 개수

        for(int i=0;i<t;i++){
            n = Integer.parseInt(br.readLine());
            arr = new ArrayList<>();
            graph = new ArrayList<>();
            queue = new LinkedList<>();
            for(int j=0;j<n+2;j++){
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                arr.add(new Point(x,y));
            }

            for(int j=0;j<n+2;j++){
                graph.add(new ArrayList<>());
            }
            for(int j=0;j<arr.size();j++){
                for(int k=j+1;k<arr.size();k++){
                    if(Math.abs(arr.get(j).x-arr.get(k).x)+Math.abs(arr.get(j).y-arr.get(k).y)<=1000){
                        graph.get(j).add(k);
                        graph.get(k).add(j);
                    }
                }
            }
            visited = new boolean[n+2];

            if(bfs(0,n)) System.out.println("happy");
            else System.out.println("sad");

        }

    }
}

맥주 20병으로 1000m를 갈 수 있다. 두 점 사이의 거리가 1000m이하인 경우 이동가능 한 곳으로 연결 해 놓는다.

이후는 bfs로 탐색하면서 목적지에 도달을 하면 happy, 도달하지 못하면 sad를 출력하면 된다.

처음 문제를 고민할 때에는 탐색하는 좌표마다 그 때의 맥주 개수를 다 계산하려 했는데 두 점 사이의 거리만 고려하면 된다니,,

생각해보니 어차피 1000m가 넘으면 가지를 못하는 것이었다.

다양한 문제를 만나며 생각의 폭을 넓혀야겠다.