(백준) 맥주마시면서걸어가기_9205 [java]

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

 

🐢 설명

2차원 평면에서 출발지점, 복수의 중간 지점, 목적지가 있을 때 이동사거리 내에 있다면 이동을 하면서 목적지까지 갈 수 있는지 푸는 문제이다.

 

맥주 20개에 하나당 50미터를 갈 수 있고, 편의점에 들릴때마다 충전할 수 있다고 했지만 간단히 말해서 현재 위치에서 다른 점까지의 DIST가 1000이하면 갈 수 있고 아니면 못간다로 받아들이면 된다.

 

따라서 출발점, 도착점, 중간 편의점들을 모두 하나의 리스트에 담고, 출발점을 큐에 넣고 방문처리 후 탐색을 한다.

 

큐에서 점 하나를 뽑고 (처음에는 당연히 출발점이다.) 해당 점에서 방문을 안했고 갈 수 있다면 큐에 넣어준다.

 

이때 큐는 우선순위 큐로 특정 점에서 목적지 점까지의 거리가 가까운 순으로 정렬된다. 따라서 갈 수 있는 점 중 목적지에 가장 가까운 점부터 확인해가면서 목적지로 가게 된다.

 

🐢코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int T;
    static boolean[] visited;
    static ArrayList<SPOT> spots = new ArrayList<>();
    static PriorityQueue<SPOT> pq;
    static StringBuilder answer = new StringBuilder();

    private static class SPOT {
        int x, y;

        public SPOT(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        T = Integer.parseInt(br.readLine());

        while (T-- > 0)
        {
            spots.clear();

            int storeCnt = Integer.parseInt(br.readLine());
            for (int i = 0; i < storeCnt + 2; i++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                spots.add(new SPOT(x, y));
            }

            visited = new boolean[storeCnt + 2];
            go();
        }
        System.out.println(answer);
    }

    private static void go() {
        int move = 1000;
        pq = new PriorityQueue<>(Comparator.comparingInt(spot -> hereTolDist(spot, spots.get(spots.size() - 1))));
        pq.add(spots.get(0));
        visited[0] = true;

        while (!pq.isEmpty()) {
            SPOT now = pq.poll();

            if (hereTolDist(now, spots.get(spots.size() - 1)) <= move) {
                answer.append("happy").append("\n");
                return;
            }

            for (int i = 1; i < spots.size(); i++) {
                if (!visited[i]) {
                    if (hereTolDist(now, spots.get(i)) <= move) {
                        visited[i] = true;
                        pq.add(spots.get(i));
                    }
                }
            }
        }
        answer.append("sad").append("\n");
    }

    private static int hereTolDist(SPOT home, SPOT target) {
        return Math.abs(home.x - target.x) + Math.abs(home.y - target.y);
    }
}

🐢 마무리