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

문제 설명

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

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

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

입력

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

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

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

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

출력

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

 

생각

DFS를 이용해서 문제를 풀었다. 처음에 맥주가 20개가 있으므로 최대로 1000미터를 움직일 수 있다. 또한 편의점에 도착했을 때 맥주를 최대한으로 살 수 있으므로, 편의점을 들르면 1000미터를 움직일 수 있다고 가정하겠다.

 

내가 생각한 방식은 다음과 같다.

1. 지금 내 위치에서 가장 가까운 편의점으로 간다.

2. 그 위치에서 다시 가장 가까운 편의점으로 이동한다. (DFS 이용)

3. 만약 나의 위치가 페스티벌의 위치가 되면 happy를 출력하고, Queue가 empty가 될 때 까지 페스티벌에 가지 못한다면 sad를 출력한다.

 

이 문제의 경우, 각 편의점의 좌표로 주어진다. x,y의 범위가 매우 크므로 만약 2차원 배열로 푼다면 제출하자마자 시간 초과가 나는 사태를 맞이할 것이다.

 

나는 나의 위치, 편의점의 위치, 페스티벌의 위치를 각각 ArrayList에 담았다. 순서대로 담게 되면,

 

집 편의점1 편의점2 편의점3 ... 편의점n 페스티벌 이런 방식으로 될 것이다.

 

배열을 돌면서 이 다음의 거리가 1000보다 작다면 다음으로 이동해서 다시 search를 하는 방식으로 문제를 풀었다.

자세한 설명을 주석에 달도록 하겠다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
 
 
public class Main {
    static int beerCount = 20;
    static int walkingDistance = beerCount * 50;
    static dot myHome;
    static dot festival;
    //내 위치, 편의점 위치, 페스티벌 위치를 담는 배열을 만든다.
    static ArrayList<dot> beers;
    static boolean[] visited;
    static boolean flag = true;
    static String result;
    static StringBuilder sb;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        int t = Integer.parseInt(br.readLine());
        for(int q=0; q<t; q++) {
            result = "sad";
            int beer = Integer.parseInt(br.readLine());
            beers = new ArrayList<dot>();
            String[] home = br.readLine().split(" ");
            myHome = new dot(Integer.parseInt(home[0]), Integer.parseInt(home[1]));
            beers.add(myHome);
            
            for(int i=0; i<beer; i++) {
                String[] str = br.readLine().split(" ");
                beers.add(new dot(Integer.parseInt(str[0]), Integer.parseInt(str[1])));
            }
            
            home = br.readLine().split(" ");
            festival = new dot(Integer.parseInt(home[0]), Integer.parseInt(home[1]));
            beers.add(festival);
            visited = new boolean[beers.size()];
            //내 위치(index:0) 부터 탐색을 시작한다.
            search(0);
            sb.append(result);
            sb.append("\n");
        }
        
        System.out.println(sb.toString());
    }
    
    public static void search(int index) {
        visited[index] = true;
        dot d = beers.get(index);
        int x = d.x;
        int y = d.y;
        //재귀적으로 dfs를 이용할 것이므로, index가 페스티벌의 위치가 되면 종료한다.
        if(index == beers.size()-1) {
            result = "happy";
            return;
        }
        
        //방문한 편의점이 아니라면 각 distance를 구해 내가 걸을 수 있는 최대 거리 (1000)보다 작으면
        //다음 편의점으로 이동하면 된다.
        //만약 거리가 더 커서 이동하지 못한다면 함수를 호출하지 못하고 for문을 다 돌게되면 종료될 것이다.
        for(int i=0; i<beers.size(); i++) {
            if(!visited[i]) {
                int distance = Math.abs(x - beers.get(i).x) + Math.abs(y - beers.get(i).y);
                
                if(walkingDistance >= distance) {
                    search(i);
                }
            }
        }        
    }
 
}
 
class dot {
    int x;
    int y;
    
    public dot(int x, int y) {
        this.x = x;
        this.y = y;
    }
}