[백준] 9205번 맥주 마시면서 걸어가기

문제 푸는 데에는 큰 시간이 안 걸렸는데 사실 뭔 말인지 이해가 잘 안 가서 거기서 10분 정도 가만히 있었던 것 같다.

문제 내용)
송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 즉, 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다.
상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다. 편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다.
편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.

1. 일단 친구들이랑 상근이랑 같이 생각할 필요가 없음. 맥주 한 박스는 상근이 거임. 그래서 상근이는 맥주 1박스 = 맥주 20병이 있으니까 1000미터를 한 번에 갈 수 있음.
2. 이후에는 그냥 bfs로 생각했을 때, 1000m 이내 편의점이면 갈 수 있고 편의점을 들르면 맥주 20개가 충전되니 또 1000m 이내 편의점을 들르면 됨. 결국 bfs로 편의점도 들르면서 동시에 현재 위치랑 락페 위치도 비교하면 됨. (1000m 이내!)

결론: 친구들로 생각하지 말고 개인당 맥주 20병 있다고 생각하면 1000m 이내에 있는 편의점만 들러서 현재 위치랑 락페 위치랑 비교하면 됨. (여기서부터는 그냥 bfs)

문제 설명이 좀 뭔말인지 모르겠다고 느껴진다.

내 코드)

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

class Graph{
    List<int[]> stores=new ArrayList();
    int n;

    public Graph(int n){
        this.n=n;
    }

    void addEdge(int x, int y){
        int[] edge={x, y};
        stores.add(edge);
    }

    int getDist(int[] e1, int[]e2){
        return getAbs(e1[0]-e2[0])+getAbs(e1[1]-e2[1]);
    }

    int getAbs(int val){
        if (val<0)
            return val*-1;

        return val;
    }

    String bfs(int[] start, int[] target){
        LinkedList<int[]> queue=new LinkedList();
        boolean[] visited=new boolean[n]; //0~n-1까지 stores에 적재된 순으로

        queue.add(start);

        while(queue.size()!=0){
            int[] now=queue.poll();
            int distToTarget=getDist(now, target);

            if(distToTarget<=1000)
                return "happy";

            for(int i=0;i<n;i++){
                int[] candidate=stores.get(i);

                //1000m이내 + 가보지 않은 곳
                int dist=getDist(now, candidate);
                if(dist<=1000 && !visited[i]){
                    queue.add(candidate);
                    visited[i]=true;
                }
            }
        }

        return "sad";
    }
}

public class Main{
    public static void main(String[] args) throws Exception{
        List<String> result=new ArrayList<>();

        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int t=Integer.parseInt(br.readLine());
        StringTokenizer st;

        for(int i=0;i<t;i++){
            int n=Integer.parseInt(br.readLine());

            st=new StringTokenizer(br.readLine());
            int hx=Integer.parseInt(st.nextToken());
            int hy=Integer.parseInt(st.nextToken());
            int[] start={hx, hy};

            Graph graph=new Graph(n);
            for(int j=0;j<n;j++){
                st=new StringTokenizer(br.readLine());
                int x=Integer.parseInt(st.nextToken());
                int y=Integer.parseInt(st.nextToken());
                graph.addEdge(x, y);
            }

            st=new StringTokenizer(br.readLine());
            int fx=Integer.parseInt(st.nextToken());
            int fy=Integer.parseInt(st.nextToken());
            int[] target={fx, fy};

            result.add(graph.bfs(start, target));
        }

        Iterator<String> it=result.listIterator();
        while(it.hasNext()){
            System.out.println(it.next());
        }
    }
}