BOJ_S1_9205

📁 [S1_9205] 맥주 마시면서 걸어가기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int N, sx, sy, dx, dy;

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

        // 테스트 케이스
        int TC = Integer.parseInt(br.readLine());

        for (int tc = 0; tc < TC; tc++) {

            // 편의점 개수
            N = Integer.parseInt(br.readLine());

            // 편의점만 저장하는 배열
            List<int[]> list = new ArrayList<>();

            for (int i = 0; i < N + 2; i++) {
                st = new StringTokenizer(br.readLine(), " ");

                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());

                // 출발점
                if (i == 0) {
                    sx = x;
                    sy = y;
                }
                // 도착점
                else if (i == N + 1) {
                    dx = x;
                    dy = y;
                }
                // 편의점
                else {
                    list.add(new int[] {x,y});
                }
            }

            // bfs의 결과값에 따라 출력
            String str = "";
            if(bfs(list)){
                str = "happy";
            }
            else{
                str = "sad";
            }
            sb.append(str).append("\n");
        }
        System.out.print(sb);
    }

    // bfs
    static boolean bfs(List<int[]> list) {
        // 방문체크
        boolean[] v = new boolean[N];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {sx, sy});

        while (!q.isEmpty()) {
            int[] d = q.poll();
            // 현재 좌표 값
            int px = d[0];
            int py = d[1];

            // 마지막
            // 맥주가 남는 경우
            if (Math.abs(px - dx) + Math.abs(py - dy) <= 1000) {
                return true;
            }

            // 편의점 돌기
            for (int i = 0; i < N; i++) {
                // 방문 안한 경우
                if (!v[i]) {
                    // list에서 값 가져온다
                    int nx = list.get(i)[0];
                    int ny = list.get(i)[1];

                    // 거리 체크
                    // 맥주가 남는 경우
                    if (Math.abs(px - nx)  + Math.abs(py - ny) <= 1000) {
                        v[i] = true;
                        q.add(new int[] {nx, ny});
                    }
                }
            }
        }
        return false;
    }
}

🤔 나의 생각

처음에 문제를 잘못이해했다..
그냥 순서가 정해져있는줄 알았는데 그게 아니였다.. ㅋㅋㅋ 이미 문제를 일반적인 방법으로 다 풀고 틀리고 나서 깨달은 것 .. ㅋㅋ
그래서 보니 편의점 가는 순서가 상관 없는 것을 보고 bfs를 통해 구현했다.
주의할 점은 x,y 값을 통해 거리를 구해서 20*50은 1000이므로 1000보다 작으면 맥주를 먹을 수 있으므로 true이고 1000을 넘으면 맥주를 못 먹으므로 false이다.