[Algorithm] boj_9205 (BFS)

문제

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

접근 방법

어떤 편의점을 먼저 들르는게 유리할지 모르기때문에, 편의점과의 거리를 계산해서 그리디로 푸는건 불가능하다. bfs로 모든 좌표들을 탐색하는것도 범위가 너무 크기때문에 불가능하다.

편의점마다 구매 가능한 맥주의 개수가 항상 같기 때문에, 다른 좌표는 탐색하지 않고 편의점들을 bfs 탐색해서 풀 수 있다.

• 현재 위치에서 이동 가능한 모든 편의점 중, 방문하지 않은 곳을 모두 queue에 넣으며 bfs 탐색.

• a-b로 가거나, b-c로 가거나, 어차피 b에 도달하면 맥주가 꽉 찬다
  -> 각 좌표마다 방문 여부를 구별할 필요 없다. (다른 노드에서 b에 도달하면 방문처리)

코드

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

public class boj_9205_bfs {

    static int T, N;
    static Point[] stores;
    static boolean[] storeVisited;
    static Queue<Point> q;
    static Point sangeuni;
    static Point festival;
    static boolean isPossible;
    static BufferedReader br;

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

        while (T-- > 0) {
            input();

            //어떤 편의점을 먼저 들르는게 유리할지 모르기때문에, 편의점과의 거리를 계산해서 그리디로 푸는건 불가능할것같다.
            //그러니까 bfs로 모든 좌표(2차원 배열)를 탐색하는게 아닌, 편의점들을 탐색하는것!!

            q.offer(sangeuni);
            bfs();

            System.out.println(isPossible ? "happy" : "sad");
        }
    }

    private static void bfs() {
        while (!q.isEmpty()) {
            Point cur = q.poll();

            //a-b로 가거나, b-다른곳 으로 가거나, 어차피 b에 도달하면 맥주가 꽉 찬다
            //-> 방문 여부를 구별할 필요 없다. (다른 노드에서 b에 도달하면 그냥 방문처리 하면 됨)

            //현재 위치에서 페스티벌까지 도착 가능한 경우
            if (isMovable(cur, festival)) {
                isPossible = true;
                break;
            }

            //다음 위치로 가능한 편의점 모두 q에 offer
            for (int i = 0; i < N; i++) {
                Point nPoint = stores[i];

                if (storeVisited[i]) {
                    continue;
                }

                //이동 가능한 편의점이라면
                if (isMovable(cur, nPoint)) {
                    q.offer(nPoint);
                    storeVisited[i] = true;
                }
            }
        }
    }

    private static boolean isMovable(Point cur, Point next) {
        return Math.abs(cur.x - next.x) + Math.abs(cur.y - next.y) <= 1000;
    }

    private static class Point {
        int x, y;

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

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

        q = new LinkedList<>();
        stores = new Point[N];
        storeVisited = new boolean[N];
        isPossible = false;

        //input sangeuni
        StringTokenizer st = new StringTokenizer(br.readLine());
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());
        sangeuni = new Point(x, y);

        //input stores
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            stores[i] = new Point(x, y);
        }

        //input festival location
        st = new StringTokenizer(br.readLine());
        x = Integer.parseInt(st.nextToken());
        y = Integer.parseInt(st.nextToken());
        festival = new Point(x, y);
    }
}