[BOJ/Java] 9205. 맥주 마시면서 걸어가기

[BOJ/Java] 9205. 맥주 마시면서 걸어가기

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

---

문제 해석

이 문제는 페스티벌에 참여하기 위해 맥주를 마시면서 여러 장소를 거쳐가는 과정을 모델링한 그래프 탐색 문제이다. 주어진 장소들 사이의 거리를 기반으로 맥주 한 캔으로 갈 수 있는 최대 거리(1000미터)를 고려해, 출발지(집)에서 목적지(페스티벌)까지 도달 가능한지 판단해야 한다.

풀이 과정

1. 주어진 모든 위치를 Vertex 객체로 저장하고, 각 위치 간의 거리를 계산해 연결 가능한 정점을 결정한다. 이 때, 맨해튼 거리가 1000 이하일 때 두 정점은 연결된다.
2. 그래프를 인접 리스트로 구성하여 각 정점이 연결된 다른 정점들의 목록을 유지한다.
3. 깊이 우선 탐색(DFS)를 사용하여 집에서 시작해 페스티벌 위치까지 경로가 존재하는지 확인한다. 탐색 도중 페스티벌 위치에 도달하면 탐색을 중지하고 'happy'를 반환한다. 그렇지 않으면 'sad'를 반환한다.

코드

package edu.ssafy.im.BOJ.Gold.G5.No9205;

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    private static int N;  // 위치 수
    private static ArrayList<Vertex> vertexList;  // 모든 위치를 저장하는 리스트
    private static ArrayList<ArrayList<Integer>> graph;  // 그래프를 인접 리스트로 표현
    private static boolean[] visited;  // 방문 여부를 확인하는 배열
    private static boolean flag;  // 페스티벌에 도달했는지 여부를 나타내는 플래그

    static class Vertex {
        int x, y;  // 위치의 x, y 좌표

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int TC = Integer.parseInt(br.readLine());

        for (int T = 0; T < TC; T++) {
            N = Integer.parseInt(br.readLine());

            vertexList = new ArrayList<>();
            for (int i = 0; i < N + 2; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                vertexList.add(new Vertex(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
            }

            sb.append(sol()).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static String sol() {
        graph = new ArrayList<>();
        for (int i = 0; i < vertexList.size(); i++)
            graph.add(new ArrayList<>());

        makeEdge();  // 간선 생성

        visited = new boolean[N+2];
        flag = false;
        dfs(0);  // DFS 시작

        if (flag) return "happy";
        return "sad";
    }

    private static void dfs(int k) {
        visited[k] = true;
        if (flag) return;
        if (k == N+1) {
            flag = true;
            return;
        }

        for (int i = 0; i < graph.get(k).size(); i++) {
            int next = graph.get(k).get(i);
            if (!visited[next]) dfs(next);
        }
    }

    private static void makeEdge() {
        for (int i = 0; i < vertexList.size(); i++) {
            Vertex current = vertexList.get(i);
            for (int j = i + 1; j < vertexList.size(); j++) {
                Vertex next = vertexList.get(j);
                if (Math.abs(current.x - next.x) + Math.abs(current.y - next.y) <= 1000) {
                    graph.get(i).add(j);
                    graph.get(j).add(i);  // 양방향 간선 추가
                }
            }
        }
    }
}

시간 복잡도 분석

주어진 정점의 수에 따라 각 정점 쌍 간의 연결 가능성을 검사하는 부분은 𝑂(𝑁^2)의 시간 복잡도를 가지며, DFS는 최악의 경우 모든 정점을 방문하므로 𝑂(𝑉+𝐸)의 시간이 소요된다. 하지만, 여기서 𝑉와 𝐸는 정점과 간선의 수를 나타낸다.

느낀점

이 문제는 그래프를 사용한 경로 탐색 알고리즘을 실제 문제에 적용하는 방법을 이해하는 데 도움을 준다. 또한, 실제 생활과 관련된 문제 상황을 모델링하는 방법에 대한 인사이트를 제공한다.