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

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static class Pos {
        int r;
        int c;

        public Pos(int r, int c) {
            this.r = r;
            this.c = c;
        }

    }

    static int T, N;
    static Pos start, end;
    static ArrayList<Pos> list;
    static boolean[] used;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        StringBuilder sb = new StringBuilder();
        T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            init(br);
            process(sb);
        }
        print(sb);
    }

    private static void init(BufferedReader br) throws IOException {
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        used = new boolean[N];
        list = new ArrayList<>();
        // 상근이네 집
        st = new StringTokenizer(br.readLine());
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());
        start = new Pos(x, y);
        // 편의점 좌표
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            Pos pos = new Pos(x, y);
            list.add(pos);
        }
        // 페스티벌 좌표
        st = new StringTokenizer(br.readLine());
        x = Integer.parseInt(st.nextToken());
        y = Integer.parseInt(st.nextToken());
        end = new Pos(x, y);
    }

    private static void process(StringBuilder sb) {
        if (bfs()) sb.append("happy\n");
        else sb.append("sad\n");
    }

    private static boolean bfs() {
        Queue<Pos> q = new LinkedList<>();
        q.add(start);
        while (!q.isEmpty()) {
            Pos now = q.poll();
            int r = now.r;
            int c = now.c;
            // 도착 검사
            int dist = getDist(r, c, end.r, end.c);
            if (dist <= 1000) return true;
            for (int i = 0; i < N; i++) {
                Pos next = list.get(i);
                int nr = next.r;
                int nc = next.c;
                dist = getDist(r, c, nr, nc);
                if (isImpossible(dist, i)) continue;
                used[i] = true;
                q.add(new Pos(nr, nc));
            }
        }
        return false;
    }

    private static int getDist(int r, int c, int nr, int nc) {
        return Math.abs(nr - r) + Math.abs(nc - c);
    }

    private static boolean isImpossible(int dist, int i) {
        return 1000 < dist || used[i];
    }

    private static void print(StringBuilder sb) {
        System.out.println(sb);
    }
}

📄 해설

• BFS 를 사용하여 해결하는 문제. BFS 로 접근을 하고, 거리 계산까지 접근을 했다면 쉽게 해결이 가능할 것(사실 이게 어려울 듯)
• 문제의 조건 : 맥주 한병 당 50미터 이동 가능, 맥주는 최대 20병까지 들고 있을 수 있으며, 맥주는 편의점에 도착하면 다시 살 수 있음
  • 조건에 따른 접근
    현재 지점에서 다음 지점(편의점, 페스티벌) 까지의 거리가 1000 이하이면 이동이 가능
• 상근이의 집(이후 시작위치), 편의점, 페스티벌(이후 종료 위치)의 위치를 입력받고, 편의점은 리스트에 담아두고, 방문 배열을 생성
• 입력 및 초기화 이후 수행 과정
  1. 시작 위치 start 에서 BFS 탐색 시작
  2. 큐에서 꺼낼때마다 페스티벌 위치 end 에 도착이 가능한지 확인
     2-1 현재 위치에서 갈 수 있으면 true 를 반환하고 탐색 종료
     2-2 현재 위치에서 갈 수 없으면 편의점 리스트 중 갈 수 있는 곳(방문하지 않았고, 거리가 1000 이하인 편의점)을 큐에 담고 반복
  3. 2의 과정을 다 수행하였음에도 중간에 종료되지 않은 경우는 갈 수 없는 경우임(큐에서 꺼낼 때 도착이 가능하면 탐색을 종료하므로)