이번에 풀어본 문제는
백준 9205번 맥주 마시면서 걸어가기 입니다.

📕 문제 링크

❗️코드

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

class Point
{
    int x,y;

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

}
public class Main {
    static int N;
    static List<List<Integer>> map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        while(t-- > 0)
        {
            // 편의점 개수
            N = Integer.parseInt(br.readLine());

            Point [] nodes = new Point[N+2];
            //정점들의 좌표 입력
            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());

                nodes[i] = new Point(x,y);
            }

            map = new ArrayList<>();
            for(int i = 0; i < N+2; ++i) map.add(new ArrayList<>());

            // 거리가 1000 이하인 정점끼리 연결
            for(int i = 0; i < N+1; ++i)
            {
                for(int j = i+1; j < N+2; ++j)
                {
                    int diff = Math.abs(nodes[i].x - nodes[j].x) + Math.abs(nodes[i].y - nodes[j].y);
                    if(diff <= 1000)
                    {
                        map.get(i).add(j);
                        map.get(j).add(i);
                    }
                }
            }
            sb.append(bfs()).append("\n");
        }
        System.out.print(sb);
    }
    static String bfs()
    {
        Queue<Integer> q = new LinkedList<>();
        q.add(0);

        boolean [] visited = new boolean[N+2];
        visited[0] = true;

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

            if(cur == N+1) return "happy";
            for(int i : map.get(cur))
            {
                if(visited[i]) continue;
                visited[i] = true;
                q.add(i);
            }
        }
        return "sad";
    }
}

📝 풀이

목적지까지 도달하는데, 50미터마다 맥주를 한 병씩 먹어줘야 하는 조건의 문제입니다.
각 정점들의 좌표를 입력받고, 정점간의 거리를 절댓값으로 계산합니다. 두 정점의 거리 차이가 1000이하라면 이동할 수 있는 것이므로 두 정점을 연결해줍니다.
모든 정점의 연결이 끝났다면, bfs탐색을 진행해주면 됩니다.
입력 순서에 따라 N+1번째 정점이 도착정점이므로, 탐색 중 N+1정점에 도달했다면 happy를 리턴해주고, 도달하지 못하고 반복이 종료되었다면 sad를 리턴해주면 됩니다.

📜 후기

복잡해보이는 문제 설명에 비해서 꽤 풀만한 문제였다고 생각합니다. 쫄지않기!