[백준] 9205 - 맥주 마시면서 걸어가기 | Java

📌 문제 정보

[9205번: 맥주 마시면서 걸어가기]

💡 접근 방식

주어진 좌표 외의 공간은 고려하지 않아도 된다려하지 않아도 된다.
거리가 1000m 이내인 좌표를 양방향으로 연결하여 펜타포트까지 갈 수 있는지 확인하면 된다.

1. ArrayList A에 주어진 좌표들을 저장한다.
2. 모든 좌표를 돌며 연결 가능 좌표( 거리가 1000m 이하 )의 인덱스를 양방향으로 beer에 저장한다.
3. bfs로 beer를 돌면 끝!

걸어갈 수 있는 거리에서 락페가 열린다니.. 거기에 맥주까지 마시면서 간다니..... 상근이가 너무 부럽다!!!!!!! 근데 50m마다 한 병이면 편의점 위치보다 화장실 위치를 먼저 조사해야 하지 않을까?

✅ 코드

import java.util.*;

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

public class Main {

    static ArrayList<int[]> A;
    static ArrayList<Integer>[] beer;

    static boolean[] visited;

    static int penta;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();


        for (int T = 0; T < t; T++) {
            int n = Integer.parseInt(br.readLine());
            int[] temp = new int[2];
            A = new ArrayList<>();
            beer = new ArrayList[n + 2];

            // 집, 편의점, 펜타
            for (int i = 0; i < n + 2; i++) {
                st = new StringTokenizer(br.readLine());
                temp = new int[2];
                temp[0] = Integer.parseInt(st.nextToken());
                temp[1] = Integer.parseInt(st.nextToken());

                A.add(temp);
                beer[i] = new ArrayList<>();

            }
            visited = new boolean[n + 2];
            penta = n+1;



            for (int i = 0; i < n + 1; i++) {
                int x = A.get(i)[0];
                int y = A.get(i)[1];
                for (int j = i + 1; j < n + 2; j++) {
                    int nx = A.get(j)[0];
                    int ny = A.get(j)[1];

                    if (1000 >= (Math.abs(x - nx) + Math.abs(y - ny))) {
                        beer[i].add(j);
                        beer[j].add(i);
                    }
                }
            }

            sb.append(bfs() ? "happy" : "sad").append("\n");

        }

        System.out.println(sb);

    }

    public static boolean bfs() {
        Queue<Integer> q = new LinkedList<>();
        q.add(0);
        visited[0] = true;

        while (!q.isEmpty()) {
            int cur = q.poll();

            if (cur == penta) {
                return true;
            }

            for (Integer i : beer[cur]) {
                if (!visited[i]) {
                    q.add(i);
                    visited[i] = true;
                }
            }
        }

        return false;
    }



}

🧠 배운 점 & 회고

실행을 해보았는데 NPE가 떠서 당황했다. 그래프 문제를 오랜만에 풀어서 그런지 ArrayList 배열인 beer의 각 인덱스에 대해 ArrayList를 초기화하지 않았던 것이 문제였다.
배열 선언만으론 각 요소가 null이기 때문에, 반드시 초기화를 해줘야 한다!
잔실수를 조심하자~

🧾 결과