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

 

목차

문제 정보

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

9205번: 맥주 마시면서 걸어가기

난이도 : G5

유형 : 그래프 탐색, BFS

---

문제 풀이

필자는 BFS로 해결했다.

이 문제에서 20개의 병의 개수 조건이 있지만 신경 쓸 필요가 없다.

왜냐하면 상근이는 도착지 외엔 편의점만 경유하기 때문이고 편의점에 들르기만 하면 다시 병 20개를 채울 수 있기 때문에

병의 갯수와 상관없이 현재 위치에서 다음위치까지의 맨해튼 거리가 1000 이하이면 항상 이동할 수 있다.

따라서 x좌표와 y좌표만 신경쓰면 된다.

 

핵심 : 현재 위치에서 다음 위치와의 거리가 1000 이하이면 다음 위치 정보를 큐에 넣으면서 반복 후 도착 위치까지 도달하는지 판별

---

코드

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

public class Main {

    public class Place {
        int x;
        int y;

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

    private final String[] message = {"happy", "sad"};
    private int t;
    private int n;
    private Place[] places;
    private boolean[] isVisited;

    public boolean passable(Place a, Place b) {
        int distance = Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
        if (distance <= 1000) {
            return true;
        } else {
            return false;
        }
    }

    public boolean bfs() {
        isVisited = new boolean[n + 2];
        Queue<Place> que = new LinkedList<>();
        que.add(new Place(places[0].x, places[0].y));
        isVisited[0] = true;

        while (!que.isEmpty()) {
            Place cur = que.poll();

            for (int i = 1; i < n + 2; i++) {
                if (isVisited[i]) {
                    continue;
                }
                if (!passable(cur, places[i])) {
                    continue;
                }

                if (i == n + 1) {
                    return true;
                }
                que.add(new Place(places[i].x, places[i].y));
                isVisited[i] = true;
            }
        }
        return false;
    }

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            n = Integer.parseInt(br.readLine());
            places = new Place[n + 2];
            for (int i = 0; i < n + 2; i++) {
                st = new StringTokenizer(br.readLine());
                places[i] = new Place(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            }

            if (!bfs()) {
                sb.append(message[1]);
            } else {
                sb.append(message[0]);
            }
            sb.append('\n');
        }

        System.out.print(sb);
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}