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

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

문제

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

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

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

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

        int T = Integer.parseInt(reader.readLine());        // 테스트케이스

        for (int t = 0; t < T; t++) {
            int n = Integer.parseInt(reader.readLine());    // 편의점 수

            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            int houseX = Integer.parseInt(tokenizer.nextToken());    // 집 x 좌표
            int houseY = Integer.parseInt(tokenizer.nextToken());    // 집 y 좌표

            int[][] map = new int[n + 1][2];

            for (int i = 0; i < n + 1; i++) {
                tokenizer = new StringTokenizer(reader.readLine());
                int x1 = Integer.parseInt(tokenizer.nextToken());   // 편의점 x 좌표
                int y1 = Integer.parseInt(tokenizer.nextToken());   // 편의점 y 좌표

                map[i][0] = x1;
                map[i][1] = y1;
            }

            Queue<int[]> queue = new ArrayDeque<>();
            queue.offer(new int[] { houseX, houseY });  // 처음 좌표 세팅

            String message = "sad";

            boolean[] visited = new boolean[n + 1];

            while (!queue.isEmpty()) {
                int[] curr = queue.poll();
                int x = curr[0];
                int y = curr[1];

                // 도착한 경우
                if (x == map[n][0] && y == map[n][1]) {
                    message = "happy";
                    break;
                }

                for (int i = 0; i < n + 1; i++) {
                    if (Math.abs(map[i][0] - x) + Math.abs(map[i][1] - y) <= 1000 && !visited[i]) {
                        visited[i] = true;
                        queue.offer(map[i]);
                    }
                }
            }

            sb.append(message).append("\n");
        }

        System.out.println(sb);
    }

}

• BFS를 활용하여 해결한 문제이다.
• 처음에 뭔가 오류가 있을 것 같았지만 한번 돌려보자는 식으로 채점했는데 맞아서 신기했다.
• 집의 위치를 시작 좌표로 하여 각 좌표에서 1000m(맥주 20병 * 50m) 이내에 이동할 수 있는 편의점과 페스티벌장을 큐에 담아 bfs를 계속 수행하도록 하였다.
• 약간 의아했던 부분이 방문 처리를 하는 부분이었는데, 처음에 간단히 생각할 때 모든 이동 경로의 경우의 수를 고려하기 위해 이미 지나간 편의점을 다른 경우가 방문 처리를 하면 값이 제대로 안나올 것이라 판단하였는데, 생각의 오류였다.
• 다익스트라나 프림처럼 어디를 거쳐가든 그 해당 좌표로 이동하기만 하면 되는 것이라 바로 방문처리를 해도 괜찮았다.