[Baekjoon 33254] Hurry the Hedgehog - JAVA

[Silver I] Hurry the Hedgehog - 33254

문제 링크

성능 요약

메모리: 285960 KB, 시간: 1072 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색, 최단 경로

제출 일자

2025년 1월 30일 18:54:37

문제 설명

Hurry is a Hedgehog, who lives in the Mushroom Kingdom. He is on a mission to save Princess Plum from the evil Donkey Kong. In order to get to the Princess, Hurry must run through a hyperspace network of roads. These roads are dangerous and for every road that he walks between two intersections, he is getting attacked by Space Invaders. Luckily, at some intersections, there is a Super Mushroom that will restore Hurry's health.

Can you find the shortest path through the network of roads, such that you can eat a Super Mushroom at each intersection?

입력

The intersections are numbered between $1$ and $n$, inclusive. \ Hurry will need to start at intersection $1$ and run to intersection $n$. \ The input is structured as follows:

• One line with three integers: $1 \leq n \leq 10^5$, the number of intersections; $0 \leq m \leq 10^6$, the number of roads; and $1 \leq s \leq n$, the number of Super Mushrooms.
• One line with $\max(0, s-2)$ integers: the indices of the intersections that have a Super Mushroom (intersections $1$ and $n$ will always have a Super Mushroom and are not in this list).
•  $m$ lines with two integers each, indicating that there is a road between the two intersections with these indices.

출력

One line containing one integer, which is the number of intersections in the path that Hurry will have to run.

문제 풀이

해당 문제를 요약하면 아래와 같다.

1. 교차로(정점) 가 $n$개 있고, 도로(간선) 가 $m$개 존재한다.
2. 특정 교차로들에만 슈퍼 버섯이 놓여 있다. (문제에서 1번 교차로와 $n$번 교차로에는 항상 버섯이 존재)
3. 번 교차로 → $n$번 교차로로 가는 경로 중에서, 들르는 교차로마다 반드시 버섯이 있어야 한다.
4. 해당 경로에서 지나가는 교차로의 개수(정점 수)가 가장 작은 값을 구해야 한다.

즉, “버섯이 놓인 교차로만 통과할 수 있는 그래프”에서 최단 경로(정점 수) 를 찾는 문제다.

아래와 같이 생각하면서 코드를 짰다.

1. 버섯이 없는 교차로는 방문할 수 없으므로, 사실상 버섯이 있는 교차로들만을 노드로 하는 그래프를 생각하면 된다.
2. 각 도로(간선)를 확인하면서, 양쪽 교차로가 모두 버섯이 있을 때만 그래프에 간선을 추가한다.
3. 이렇게 축소된 그래프는, “버섯 교차로들 간의 연결 관계”가 된다.
4. 이 축소 그래프 상에서 “1번 교차로부터 $n$번 교차로”까지의 최단 거리(간선 수)를 구한다.
5. 문제에서 구해야 하는 것은 “최단 거리(간선 수)”가 아니라, 최단 경로에 포함되는 교차로의 개수(즉, 정점 수)이므로, $정점 개수 = (간선 수) + 1$를 계산하여 출력한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int s = Integer.parseInt(st.nextToken());

        boolean[] hasMushroom = new boolean[n + 1];
        hasMushroom[1] = true;
        hasMushroom[n] = true;

        String mushroomLine = br.readLine();

        if (s > 2) {
            st = new StringTokenizer(mushroomLine);
            for (int i = 0; i < s - 2; i++) {
                int x = Integer.parseInt(st.nextToken());
                hasMushroom[x] = true;
            }
        }
        ArrayList<Integer>[] graph = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            if (hasMushroom[a] && hasMushroom[b]) {
                graph[a].add(b);
                graph[b].add(a);
            }
        }

        int[] distance = new int[n + 1];
        Arrays.fill(distance, -1);
        distance[1] = 0;

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);

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

            if (cur == n) break;

            for (int nxt : graph[cur]) {
                if (distance[nxt] == -1) {
                    distance[nxt] = distance[cur] + 1;
                    queue.offer(nxt);
                }
            }
        }

        int result = (distance[n] == -1) ? 0 : distance[n] + 1;
        bw.write(String.valueOf(result));
        bw.newLine();

        bw.flush();
        bw.close();
        br.close();
    }
}

코드 풀이

StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken());

boolean[] hasMushroom = new boolean[n + 1];
hasMushroom[1] = true;
hasMushroom[n] = true;

• n 에는 교차로 수, m에는 도로 수, s에는 버섯이 놓인 교차로 개수를 저장할 변수로 선언한다.
• hasMushroom: 버섯이 있는 교차로를 표시할 배열
• 1번 교차로와 n번 교차로에는 항상 버섯이 있다고 문제에서 주었기 때문에 true로 설정한다.

        String mushroomLine = br.readLine();

        if (s > 2) {
            st = new StringTokenizer(mushroomLine);
            for (int i = 0; i < s - 2; i++) {
                int x = Integer.parseInt(st.nextToken());
                hasMushroom[x] = true;
            }
        }

• mushroomLine: - 2 개의 버섯 교차로 정보(1, n 제외)를 읽었다.
• s > 2 인 경우에만, 해당 줄을 토큰화하여 교차로 번호를 파싱했다.
• hasMushroom[x] = true를 통해 버섯 교차로를 표시했다.

ArrayList<Integer>[] graph = new ArrayList[n + 1];
for (int i = 0; i <= n; i++) {
    graph[i] = new ArrayList<>();
}

• 버섯 교차로만 이루어진 인접 리스트를 생성한다.

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            if (hasMushroom[a] && hasMushroom[b]) {
                graph[a].add(b);
                graph[b].add(a);
            }
        }

• 도로 정보 입력 + "양쪽 교차로가 모두 버섯일 때만" 그래프에 간선을 추가한다.
  • m개의 도로를 차례대로 입력받으면서, 해당 도로의 양 끝점(a, b)이 둘 다 버섯 교차로인 경우에만 연결을 맺는다.

int[] distance = new int[n + 1];
Arrays.fill(distance, -1);  // -1은 "아직 방문 안 함"을 의미
distance[1] = 0;            // 시작점(1번 교차로)의 거리 = 0

Queue<Integer> queue = new LinkedList<>();
queue.offer(1);

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

    if (cur == n) break;  // n번 교차로 도착 시 탐색 중단

    for (int nxt : graph[cur]) {
        if (distance[nxt] == -1) {
            distance[nxt] = distance[cur] + 1;
            queue.offer(nxt);
        }
    }
}

• BFS를 이용해 1번에서 n번까지의 최단 거리(간선 수) 구한다.
• distance[i]는 “1번에서 i번까지 이동할 때 거쳐야 하는 간선 수”를 저장한다.
  • 시작점 1번은 distance[1] = 0
  • 한 번 방문하면 -1이 아닌 값이 설정된다.
• 큐에서 원소를 빼면서, 현재 정점(cur)과 연결된 정점(nxt)을 차례대로 방문한다.
  • 미방문(distance[nxt] == -1) 상태라면, distance[nxt] = distance[cur] + 1 로 갱신하고 큐에 삽입한다.
• 만약 cur가 $n$번 교차로면 이미 최단 경로를 찾은 것이므로, BFS를 더 진행할 필요가 없어 중단한다.

int result = (distance[n] == -1) ? 0 : distance[n] + 1;
bw.write(String.valueOf(result));
bw.newLine();
bw.flush();

• distance[n]이 간선 개수를 의미하므로, 정점 개수(교차로 개수)는 distance[n] + 1이 된다.
• 문제에서 “경로에 포함된 교차로의 개수”를 출력하라고 했으므로, 이 값을 결과로 출력한다.
• 혹시 distance[n]가 -1이면, 1번에서 n번까지 갈 수 있는 경로가 없다는 뜻이므로, 예외적으로 0 등을 출력할 수도 있다.