맥주마시면서 걸어가기 - 9205

맥주 마시면서 걸어가기

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	34131	14159	10323	39.857%

문제

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

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

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

입력

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

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

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

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

출력

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

예제 입력 1

2
2
0 0
1000 0
1000 1000
2000 1000
2
0 0
1000 0
2000 1000
2000 2000

---

► Idea

1. 페스티벌까지 도달할 수 있는 조건

1. 집에서 페스티벌까지 거리가 1000m 이내이다.
2. 집에서 ↔ 페스티벌 사이에 편의점이 N개가 있고, 집↔ N개의 편의점 ↔ 페스티벌 까지의 간격이 1000m 이내이다.

막상 문제를 보면 단순하게 생각하는 게 가장 어려운데, 단순하게 생각하면 된다.

맥주 한 병당 50m를 갈 수 있고, 갖고 있는 맥주는 1박스에 총 20개가 들어있다. 그러면 각 Location 사이가 무조건 1000m 이내여야 한다.

2. 좌표 탐색

각 좌표를 저장하고, 다음 노드까지의 거리가 1000m 이내이면 갈 수 있는 후보이다.

3. 탐색 알고리즘 DFS, BFS 중 어떤 것을 사용할 것 인지?

DFS에 조금 더 익숙했었기에, 우선 DFS를 써야겠다고 생각했다.

처음에 문제를 보고 안 풀려서 일단 끄고, 도서관에서 내려오는 길에서 직접 걸으면서 생각을 했다.“어 이건 BFS다”라고 생각하고 집 와서 풀었다.

• 왜 BFS인가?

  여기 되네? 되네? 하면서 깊이 들어가는 것보다 중간에 못 갈수도 있으니 일단 갈 수 있는곳은 다 저장해 놓는다. 그리고 안 되면? 바로 갈 수 있었던(마지막 분기점)곳으로 돌아온다.

  • 가능한 모든 루트 중, 각 분기 사이의 거리가 1000m 이상이면 그 루트는 아예 갈 수 없다.
  • 따라서, DFS로 한 경로를 깊이 따라가는 것 보다
  • BFS로 다음 위치가 1000m 이상이라면 Queue에 삽입하지 않는다. 즉, 고려하지 않는다.

---

► Code

public class Main {
    //테케
    static int tc;
    //가로, 세로 길이
    static int n, m;
    //좌표 저장
    static ArrayList<Point> list;
    static boolean[] visited;

    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        tc = Integer.parseInt(br.readLine());
        sb = new StringBuilder();

        //인접행렬 입력받기
        for (int i = 0; i < tc; i++) {
            //편의점 개수
            int store_count = Integer.parseInt(br.readLine());
            list = new ArrayList<Point>();
            visited = new boolean[store_count + 2];

            for (int m = 0; m < store_count + 2; m++) {

                String[] node = br.readLine().split(" ");
                int a = Integer.parseInt(node[0]);
                int b = Integer.parseInt(node[1]);
                list.add(new Point(a, b));
            }
            int result = bfs(list, visited, 0, 0);
            if (result == 1) {
                sb.append("happy").append("\n");
            } else {
                sb.append("sad").append("\n");
            }
        }
        System.out.print(sb.toString().trim());
    }

    private static int bfs(ArrayList<Point> list, boolean[] visited, int x, int y) {

        //락페 좌표
        int rX = list.get(list.size() - 1).getX();
        int rY = list.get(list.size() - 1).getY();

        Queue<Point> que = new LinkedList<>();

        //시작 위치 삽입
        que.add(new Point(x, y));
        int dist = 0;

        //x,y 행렬 방문 체크
        visited[0] = true;
        while (!que.isEmpty()) {
            Point nowNode = que.poll();
            int curX = nowNode.getX();
            int nX = list.get(curX).x;
            int curY = nowNode.getY();
            int nY = list.get(curY).y;

            if (nX == rX && nY == rY) {
                return 1;
            }
            for (int s = 0; s < list.size(); s++) {
                int x2 = list.get(s).x; // 다음 좌표 x 값
                int y2 = list.get(s).y; // 다음 좌표 y 값
                dist = Math.abs(nX - x2) + Math.abs(nY - y2);
                if (dist <= 1000 && !visited[s]) {
                    visited[s] = true;
                    que.add(new Point(s, s));
                }
            }
        }
        return 0;
    }

    public static class Point {
        private final int x, y;

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

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }
    }
}

/**
 * 방문 배열 길이
 * 좌표 저장 할 자료 구조
 * 좌표 음수일 때
 */

---

► 시간 소요한 부분

반례 1

1
9
3000 3000 1
3000 2000 2 
3000 1000 3
2000 1000
1000 1000
4000 1000 4
5000 1000 5
5000 0 6
3000 0
1000 0
5000 -1000 7

1. 여기서 분기점은 (3000,1000)이다. = 한 노드에서 갈 수 있는 노드가 여러 노드일 때?
2. 둘 중 어느곳이 정답으로 가는 노드일지 모른다. 큐에 다 삽입한다. →
3. (2000,1000) 으로 가는 경로가 실패한 경로라면, 분기점에서 다른 방향의 노드를 큐에서 빼내어 다시 또 탐색을 진행한다.

---

인접 노드 탐색

처음에 좌표와 동시에 ArrayList에서 어떻게 인접 노드를 탐색할지 고민했다.

1. Point 클래스 생성하여 좌표를 저장한다.
2. (x, y) 좌표는 하나의 노드로 처리되어야 한다.
3. 처음에 2차원 배열 graph를 만들었는데, 좌표값을 받아오면서 Index out of range 에러가 자꾸 발생했다.

4. 이후 Point 클래스를 저장하는 ArrayList를 생성했다. bfs 메소드 매개변수는 list 내의 인덱스로 하고, 해당 인덱스로 방문 여부를 체크하고, 큐에 삽입했다.

    list = new ArrayList<Point>();
   

5. 그리고 bfs 메소드 내에서 Node의 객체를 생성해 x, y 좌표를 불러온다. 이 부분은 다시 봐야할 듯하다.

---