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

문제

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

---

풀이(29분)

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws Exception {
        int t = Integer.parseInt(br.readLine()); // 테스트 케이스 수

        for (int i = 0; i < t; i++) {
            System.out.println(answer());
        }
    }

    public static String answer() throws IOException {
        int storeCount = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        Point home = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())); // 집 위치
        ArrayList<Point> stores = new ArrayList<>();
        for (int i = 0; i < storeCount; i++) {
            st = new StringTokenizer(br.readLine());
            stores.add(new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }
        st = new StringTokenizer(br.readLine());
        Point festival = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())); // 축제 위치

        return bfs(home, stores, festival) ? "happy" : "sad";
    }

    public static boolean bfs(Point home, ArrayList<Point> stores, Point festival) {
        Queue<Point> queue = new LinkedList<>();
        boolean[] visited = new boolean[stores.size()];
        queue.add(home);

        while (!queue.isEmpty()) {
            Point current = queue.poll();
            if (distance(current, festival) <= 1000) {
                return true; // 축제에 도달 가능
            }

            for (int i = 0; i < stores.size(); i++) {
                if (!visited[i] && distance(current, stores.get(i)) <= 1000) {
                    visited[i] = true;
                    queue.add(stores.get(i)); // 편의점 방문
                }
            }
        }

        return false; // 축제에 도달 불가능
    }

    public static int distance(Point p1, Point p2) {
        return Math.abs(p1.x - p2.x) + Math.abs(p1.y - p2.y);
    }

    static class Point {
        int x, y;

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

 

리스트에 편의점에 대한 정보를 잘 담아둔 뒤 bfs를 사용하여 문제를 해결하였다.

 

문제 풀이 초반 Collections.sort를 커스텀하여 문제를 해결하려고 하였다. 하지만 이 경우 편의점을 쓸데없이 방문하느라 놓치는 케이스가 있었기에 bfs로 돌려 풀었다.