[백준 / Java] 9205: 맥주 마시면서 걸어가기 (BFS)

난이도: Gold 5

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

 

문제

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 즉, 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다.

상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다. 편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다.

편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 50)

각 테스트 케이스의 첫째 줄에는 맥주를 파는 편의점의 개수 n이 주어진다. (0 ≤ n ≤ 100).

다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 주어진다. 각 좌표는 두 정수 x와 y로 이루어져 있다. (두 값 모두 미터, -32768 ≤ x, y ≤ 32767)

송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리)

출력

각 테스트 케이스에 대해서 상근이와 친구들이 행복하게 페스티벌에 갈 수 있으면 "happy", 중간에 맥주가 바닥나서 더 이동할 수 없으면 "sad"를 출력한다. 

---

 

예시에는 다음과 같이 좌표 정보가 주어져 있다.

 

중요한 것은, 반드시 편의점을 들러서 페스티벌까지 갈 필요가 없다는 것이다.

집에서 편의점보다 페스티벌까지의 거리가 더 가깝다면, 곧바로 페스티벌로 갈 수 있다.

 

좌표 정보를 Point 클래스를 만들어서 Point 타입의 배열에 저장해두고, 

방문 체크를 할 boolean 타입의 배열을 만들자.

그리고, BFS 수행을 할 Queue도 만들자.

 

큐에는 맨 처음 입력받은 집의 좌표를 넣고, 집의 인덱스는 0번이므로 0번째 인덱스를 방문 체크하자.

 

큐에서 좌표를 뽑아낸다. 뽑아져 나온 좌표는 (0, 0)이다.

그리고 모든 좌표를 탐색한다.

 

해당 좌표를 방문하지 않았거나, 현재 좌표와 해당 좌표의 거리 차이가 1000 이하라면 

큐에 해당 좌표를 삽입하고, 해당 좌표에 해당하는 인덱스를 방문 체크해준다.

 

거리 차이가 1000 이하인 이유는 맥주 한 박스에는 맥주 20개가 들어있고, 50미터에 한 병씩 마셔야 하므로 20 * 50 = 1000 을 넘으면 안된다.

 

 

(1000, 0)에 해당하는 인덱스인 1을 방문하지 않았고, 큐에서 뽑은 좌표와 해당 좌표의 거리가 1000이므로

큐에 (1000, 0)을 삽입하고 1을 방문 체크해준다.

이제 다음 좌표로 넘어가자.

 

 

(1000, 1000)에 해당하는 인덱스인 2를 방문하지 않았지만, 큐에서 뽑은 좌표와 해당 좌표의 거리가 2000이므로

조건에 만족하지 않는다.

아무것도 하지 않고 다음 좌표로 넘어가자.

 

 

(2000, 1000)에 해당하는 인덱스인 3을 방문하지 않았지만, 큐에서 뽑은 좌표와 해당 좌표의 거리가 3000이므로

조건에 만족하지 않는다.

비교할 좌표가 마지막 인덱스이므로 큐에서 현재 좌표를 새로 뽑자.

 

 

큐에서 좌표를 뽑아낸다. 뽑아져 나온 좌표는 (1000, 0)이다.

방문 체크한 좌표들은 비교할 필요가 없으므로 넘어가고, 방문 체크하지 않은 좌표들을 비교한다.

 

 

(1000, 1000)에 해당하는 인덱스인 2를 방문하지 않았고, 큐에서 뽑은 좌표와 해당 좌표의 거리가 1000이므로

큐에 (1000, 1000)을 삽입하고 2를 방문 체크해준다.

이제 다음 좌표로 넘어가자.

 

 

(2000, 1000)에 해당하는 인덱스인 3을 방문하지 않았지만, 큐에서 뽑은 좌표와 해당 좌표의 거리가 2000이므로

조건에 만족하지 않는다.

비교할 좌표가 마지막 인덱스이므로 큐에서 현재 좌표를 새로 뽑자.

 

 

큐에서 좌표를 뽑아낸다. 뽑아져 나온 좌표는 (1000, 1000)이다.

방문 체크한 좌표들은 비교할 필요가 없으므로 넘어가고, 방문 체크하지 않은 좌표들을 비교한다.

(2000, 1000)에 해당하는 인덱스인 3을 방문하지 않았고, 큐에서 뽑은 좌표와 해당 좌표의 거리가 1000이므로 조건을 만족한다. 그런데 해당 좌표는 마지막 인덱스이므로, true를 리턴한다.

BFS 수행 결과가 true이므로, happy를 출력하고 끝내면 된다.

이런 식으로 모든 좌표를 다 탐색해야 한다.

 

 

주석에 설명을 한 줄 한 줄 자세히 적어 놓았다.

자, 이제 코드를 보자.

 

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 P9205_맥주마시면서걸어가기 {
    static Point[] points;        // 좌표 정보가 담긴 1차원 배열
    static boolean[] visited;    // 방문 체크 1차원 배열
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());    // 테스트 케이스의 개수
        
        // 테스트 케이스만큼 반복
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());    // 편의점의 개수
            // 좌표의 개수: 편의점의 개수 + 2 = 편의점의 개수 + 집 1개 + 페스티벌 1개
            points = new Point[n + 2];        // 좌표 배열 크기 초기화
            visited = new boolean[n + 2];    // 방문 배열 크기 초디화
            
            // 집, 편의점, 페스티벌 좌표 입력받기
            for (int j = 0; j < n + 2; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                points[j] = new Point(x, y);    // 좌표 정보를 배열에 저장
            }
            
            if (bfs()) {    // bfs 수행 결과가 true일 때
                System.out.println("happy");
            } else {        // bfs 수행 결과가 false일 때
                System.out.println("sad");
            }
        }
    }
    
    public static boolean bfs() {
        Queue<Point> queue = new LinkedList<>();    // bfs 수행을 위한 큐
        queue.add(points[0]);    // 맨 처음(집) 좌표를 큐에 삽입
        visited[0] = true;        // 맨 처음(집)의 인덱스를 방문 체크
        
        // 큐가 빌 때까지 반복
        while (!queue.isEmpty()) {
            Point now = queue.poll();    // 현재 좌표를 큐에서 뽑기
            
            // 좌표 개수만큼 반복
            for (int i = 0; i < points.length; i++) {
                // 해당 좌표를 방문하지 않았거나, 현재 좌표와 해당 좌표의 거리 차이가 1000 이하라면
                // ㄴ 1000 이하인 이유: 맥주 한 박스에는 맥주 20개가 들어있고, 50미터에 한 병씩 마셔야 하므로
                //                 20 * 50 = 1000 을 넘으면 안된다.
                if (!visited[i] && distance(now, points[i]) <= 1000) {
                    // 해당 좌표가 좌표 배열의 마지막 인덱스라면 목적지 좌표
                    if (i == points.length - 1) {    
                        return true;        // 무조건 갈 수 있으므로 true 리턴
                    }
                    queue.add(points[i]);    // 해당 좌표를 큐에 삽입
                    visited[i] = true;        // 해당 좌표의 인덱스를 방문 체크
                }
            }
        }
        
        return false;    // 더이상 갈 좌표가 큐에 없으므로 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;
        }
    }
}