백준 - 24955 숫자 이어 붙이기(Java)

bfs 문제입니다.

 

문제의 설명이 복잡하지만, 요약하면 다음과 같습니다.

• 노드의 개수는 N개이다.
• 간선의 개수는 N-1개이다. (최소신장트리)
• 각 노드마다 숫자(가중치)가 주어지는데, 시작 노드 부터 도착 노드 까지 갈 때의 숫자를 이어 붙여라. (덧셈 아닙니다. 문자열로 만들어 이어 붙이는 것입니다.)

입력을 요약하면 다음과 같습니다.

• 첫 번째 줄에는 노드의 개수인 N과 탐색 횟수인 Q가 주어진다.
• 두 번째 줄에는 각 노드의 가중치가 주어진다.
• 세 번째 줄 부터 N-1개 만큼 연결 정보(간선)이 주어진다.
• 마지막으로 Q개 만큼 탐색할 시작 노드와 도착 노드가 주어진다.

예제 입력1을 그림으로 표현하면 다음과 같습니다

예제 입력 네 번째 줄 까지가 트리의 정보입니다.

다 섯번째 줄 부터 Q개 만큼 탐색할 정보가 주어지기 때문에 이 개수만큼 반복하면 됩니다.

 

탐색은 dfs를 사용하여 시작 노드에서 부터 도착 노드까지 반복하면 됩니다.

 

※ 주의할 점

문제에서 숫자가 너무 커질 수 있으니 1,000,000,007로 나눠 나머지를 구하라고 나와있습니다.

문제의 최대치를 계속 사용한다면, Long을 사용한다 하더라도 Long으로 처리할 수 있는 범위를 넘어갑니다.

때문에 Long보다 더 큰 자료형을 써야 하는데, 그것은 BigInteger입니다.

 

[구현 코드]

import java.io.*;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    private static final int divided = 1_000_000_007;

    private static int[] weights;
    private static boolean[] visited;
    private static List<List<Integer>> graph;
    private static StringBuilder answer;

    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 stz = new StringTokenizer(br.readLine(), " ");

        int n = Integer.parseInt(stz.nextToken());
        int q = Integer.parseInt(stz.nextToken());

        // 각 집 가중치
        weights = new int[n +1];
        stz = new StringTokenizer(br.readLine(), " ");
        for(int i = 1; i< n +1; i++){
            weights[i] = Integer.parseInt(stz.nextToken());
        }

        graph = new ArrayList<>();
        for(int i = 0; i< n +1; i++){
            graph.add(new ArrayList<>());
        }

        // 간선(최소신장트리)으로 연결 정보 입력
        for(int i = 0; i< n -1; i++){
            stz = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(stz.nextToken());
            int b = Integer.parseInt(stz.nextToken());

            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        // q 만큼 반복
        answer = new StringBuilder();
        for(int i = 0; i< q; i++){
            visited = new boolean[n +1];
            stz = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(stz.nextToken());
            int b = Integer.parseInt(stz.nextToken());

            dfs(a, b, String.valueOf(weights[a]%divided));
        }

        answer.replace(answer.length()-1, answer.length(), "");
        bw.write(answer.toString());

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

    private static void dfs(int node, int destination, String sum) {
        visited[node] = true;

        if(node == destination){
            BigInteger pre = new BigInteger(sum);
            String ans = pre.remainder(new BigInteger(String.valueOf(divided))).toString();
            answer.append(ans).append("\n");
            return;
        }

        // 다음 노드 탐색
        for (int next : graph.get(node)){
            if(!visited[next]){
                dfs(next, destination, sum+weights[next]%divided);
            }
        }
    }
}