[백준/Gold V] 맥주 마시면서 걸어가기

[Gold V] 맥주 마시면서 걸어가기 - 9205

문제 링크

문제 설명

상근이와 친구들이 송도에서 열리는 펜타포트 락 페스티벌에 가기 위해 맥주를 마시며 걸어가는 문제 상근이는 집에서 출발해 페스티벌 장소까지 이동해야 하며, 50미터마다 맥주 한 병을 마셔야 합니다. 맥주는 처음에 20병이 들어있는 박스를 가지고 출발하지만, 중간에 편의점을 통해 추가로 구매할 수 있다. 편의점에서는 빈 병을 버리고 새 맥주를 살 수 있다.

거리 계산은 맨해튼 거리로 계산한다. ( |x_1 - x_2| + |y_1 - y_2| )

입력

첫째 줄: 테스트 케이스의 개수 ( t ) (1 ≤ ( t ) ≤ 50)

각 테스트 케이스 첫째 줄: 편의점의 개수 ( n ) (0 ≤ ( n ) ≤ 100) 다음 ( n + 2 )개 줄: 각 장소의 좌표 (상근이 집, 편의점들, 페스티벌)로 주어짐. 각 좌표는 두 정수 ( x )와 ( y ) (-32768 ≤ ( x, y ) ≤ 32767)

출력 각 테스트 케이스에 대해 “happy” 또는 “sad”를 출력 “happy”는 페스티벌에 도착할 수 있음을, “sad”는 맥주가 바닥나서 도중에 멈추게 되는 것을 의미한다.

문제 풀이

import java.util.*;
import java.io.*;
import java.math.*;
/**
 *
 * - 알고리즘 풀이

 * */
public class Main {

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

        int tc = Integer.parseInt(br.readLine()); // 테스트 케이스
        
        for (int i = 0; i < tc; i++) 
            canAttendFestival(br);
    }
    
    public static void canAttendFestival(BufferedReader br) throws IOException{
        StringTokenizer st;
        int convinenceStoreCount = Integer.parseInt(br.readLine()); //편의점

        st = new StringTokenizer(br.readLine());

        Node home = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), false); // 집의 위치를 받는다.

        List<Node> nodeList = new ArrayList<>(); //집이 아닌 곳들의 List
        for (int i = 0; i < convinenceStoreCount; i++) {
            st = new StringTokenizer(br.readLine());
            nodeList.add(new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), false));
        }

        //마지막은 페스티벌
        st = new StringTokenizer(br.readLine());
        nodeList.add(new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), true));

        /////////////////////// 입력 종료 ////////////////

        Queue<Node> queue = new LinkedList<>(); // 지금 가지고 있는 맥주로 갈 수 있는 Node
        queue.add(home); //처음은 집에서 시작

        // 한 Node를 기점으로 맥주를 마시면서 갈 수 있는 장소를 탐색
        while(!queue.isEmpty()) {
            Node nowLocation = queue.poll();

            if (nowLocation.isFestival) { //축제에 도착!
                System.out.println("happy");
                return;
            }

            for (Node node : nodeList) {
                if (node.visited)
                    continue;

                int distance = Math.abs(node.y - nowLocation.y) + Math.abs(node.x - nowLocation.x); // 두 지점 사이의 멘헤튼 거리

                if (distance <= 1000) {//맥주 20상자로 갈 수 있음
                    queue.add(node);
                    node.visited = true;
                }
            }
        }

        System.out.println("sad");
    }
}

class Node {
    int y, x; // 2차원 상의 Node의 좌표
    boolean visited; // 이미 방문한 편의점 인가? or 집인가
    boolean isFestival; // 페스티벌인가?

    Node(int y, int x, boolean isFestival) {
        this.y = y;
        this.x = x;
        this.isFestival = isFestival;
    }
}

핵심 로직

 Queue<Node> queue = new LinkedList<>(); // 지금 가지고 있는 맥주로 갈 수 있는 Node
        queue.add(home); //처음은 집에서 시작

        // 한 Node를 기점으로 맥주를 마시면서 갈 수 있는 장소를 탐색
        while(!queue.isEmpty()) {
            Node nowLocation = queue.poll();

            if (nowLocation.isFestival) { //축제에 도착!
                System.out.println("happy");
                return;
            }

            for (Node node : nodeList) {
                if (node.visited)
                    continue;

                int distance = Math.abs(node.y - nowLocation.y) + Math.abs(node.x - nowLocation.x); // 두 지점 사이의 멘헤튼 거리

                if (distance <= 1000) {//맥주 20상자로 갈 수 있음
                    queue.add(node);
                    node.visited = true;
                }
            }
        }

• 거리 계산: 코드는 맨해튼 거리를 사용하여 두 지점의 거리를 계산 |x_1 - x_2| + |y_1 - y_2| Java의 Math.abs()를 활용해서 계산 로직 구현

• 맥주 사용: BFS로 탐색하는 동안 최대 20병의 맥주가 있으므로, 1000미터 이내의 위치 도달 가능한 편의점 & 페스티벌 탐색 (출발 할 당시에 맥주를 마시므로 1000으로 고정 가능)

• 방문 여부 관리: visited 변수를 통해 이미 방문한 노드를 재탐색하지 않도록 하여 무한 루프를 방지

• 예상 BFS의 시간복잡도:  ( O(V + E) )