[백준] 9205번 맥주 마시면서 걸어가기 (JAVA)

문제

- 상근이네 집에서 맥주 한 박스 들고 출발

- 맥주 한 박스에는 맥주가 20개 들어있음

- 50미터에 한 병씩 마실 것임 (50미터 가기 직전에 맥주 한 병을 마셔야 함)

- 가는 길에 맥주를 더 구매해야 할 수도 있음

- 편의점에 들렀을 때, 빈 병은 버리고 새 맥주 병을 살 수 있음

- 박스에 들어있는 맥주는 20병을 넘을 순 없음

- 편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 함

- 상근이가 행복하게 목적지까지 도착할 수 있으면 "happy", 중간에 맥주가 바닥나서 더 이동할 수 없으면 "sad"를 출력

 

해결방법

맥주가 20병 있는데 1병 당 50미터를 이동할 수 있기 때문에 현재 좌표부터 다음 좌표(편의점 or 목적지)까지 1000미터 이내여야 이동이 가능하다. 따라서 현재 좌표부터 다음 좌표까지 거리를 확인하면서 이동할지를 확인한다. 

 

코드

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

// 좌표 class
class Node {
    int i;
    int j;

    public Node(int i, int j) {
        this.i = i;
        this.j = j;
    }
}

public class Main {
    static int N;
    static Node sNode, fNode;
    static List<Node> list;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int tc = 1; tc<=T; tc++) {
            list = new ArrayList<>();
            N = Integer.parseInt(br.readLine());
            for(int i = 0; i<N+2; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                // 출발 위치
                if(i == 0)
                    sNode = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
                // 도착 위치
                else if(i == N+1)
                    fNode = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
                // 중간 편의점 위치
                else
                    list.add(new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
            }
	    // 이동
            BFS();
        }
    }

    static void BFS() {
        Queue<Node> queue = new LinkedList<>();			// 이동 좌표 저장
        boolean[] visited = new boolean[N];			// 방문 처리
        queue.add(sNode);					// 출발 위치 저장
        while (!queue.isEmpty()) {
            Node now = queue.poll();		// 현재 위치
            // 현재 위치에서 도착 위치까지 1000미터 이내라면 행복하게 도착할 수 있음
            if(Math.abs(now.i - fNode.i) + Math.abs(now.j - fNode.j) <= 1000) {
                System.out.println("happy");
                return;
            }
	    // 편의점 방문
            for(int i = 0; i<N; i++) {
            	// 이제까지 방문했던 편의점인지 확인
                if(!visited[i]) {
                    // 다음 위치
                    Node next = list.get(i);
                    // 현재 위치에서 다음 편의점의 위치까지 1000미터 이내라면 편의점을 방문할 수 있음
                    if(Math.abs(now.i - next.i) + Math.abs(now.j - next.j) <= 1000) {
                        visited[i] = true;		// 방문처리
                        queue.add(next);		// 다음 방문 장소로 이동 좌표 저장
                    }
                }
            }
        }
	// 결국 도착하지 못했다면 "sad" 출력
        System.out.println("sad");
        return;
    }
}