[백준/Java] 24955 숫자 이어 붙이기

🔗 문제 링크: https://www.acmicpc.net/problem/24955

 

🔍 해결 과정

문제에서 주어진 그래프는 MST의 형태를 이루고 있습니다. 그래서 시작점에서 끝점까지의 숫자를 단순히 이어붙여서 문제를 해결할 수 있을 것이라고 생각하기 쉬우나 집의 대문에 주어지는 값의 최댓값은 10억이고, 두 개의 10억을 단순히 문자열 형태로 이어 붙여서 이를 누적해나가면 메모리 초과 문제에 걸립니다. 따라서 문자열이 아닌 Long 형태의 정수로 계산하면서 BFS를 이어가야 합니다.

 

설계 과정은 다음과 같습니다.

1️⃣ 정수형 이중 리스트 homes를 만들어 집들과의 연결 관계를 나타낸다. 
2️⃣ 정수형 배열 homeValues를 만들어 집 대문에 적혀 있는 값 정보를 담는다.
3️⃣ BFS를 활용하여 시작집부터 도착집까지 경로를 찾아가며 이어 붙인 숫자의 정보를 계속 업데이트 한다.
4️⃣ Java의 내장함수 Math.log10 기능을 활용하여 이어 붙일 숫자들의 자리를 마련하도록 한 다음 두 숫자를 더해줌으로써 숫자를 이어 붙인 형태로 만들어준다. (ex. 10, 91을 이어붙인다고 했을 때 91은 두 자리 수이므로 10을 1000으로 만든 다음 91을 더함 이 때 Math.log10에 들어갈 숫자는 91이 된다.)

 

 

📒 회고점

문자열을 무작정 이어 붙이기에는 메모리 초과 문제가 발생할 수 있으므로 섣불리 문자열로만 해결하지 말아야겠다는 생각을 했습니다.

모듈러 연산을 통해서 숫자들을 이어 붙이는 과정에서 많은 오류에 직면했기에 모듈러 연산의 핵심 공식들에 대해서 정리하였습니다.

(A + B)modC = (AmodC + BmodC)modC (해당 식은 - 연산에 대해서도 동일)
(A * B)modC = (AmodC * BmodC)modC

 

 

참고 사이트: https://sskl660.tistory.com/75

모듈러 산술(Modular Arithmetic)

 

---

✏️ 코드

import java.io.*;
import java.util.*;

class Node {
    private final int nodeNumber;
    private final long value;

    public Node(int nodeNumber, long value) {
        this.nodeNumber = nodeNumber;
        this.value = value;
    }

    public int getNodeNumber() {
        return nodeNumber;
    }

    public long getValue() {
        return value;
    }
}

public class Main {

    private static final int MOD = 1_000_000_007;

    private static List<List<Integer>> homes = new ArrayList<>();
    private static int n, q;
    private static long[] homeValues;

    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());
        StringBuilder sb = new StringBuilder();
        n = Integer.parseInt(st.nextToken());
        q = Integer.parseInt(st.nextToken());
        homeValues = new long[n + 1];

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

        st = new StringTokenizer(br.readLine());

        for (int i = 1; i <= n; ++i) {
            homeValues[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < n - 1; ++i) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

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

        for (int i = 0; i < q; ++i) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            bfs(sb, from, to);
        }

        bw.write(sb.toString());
        bw.flush();
    }

    private static void bfs(StringBuilder sb, int start, int end) {
        boolean[] visited = new boolean[n + 1];
        Queue<Node> q = new ArrayDeque<>();
        q.offer(new Node(start, homeValues[start] % MOD));
        visited[start] = true;

        while (!q.isEmpty()) {
            Node cur = q.poll();
            int curNodeNumber = cur.getNodeNumber();
            long curValue = cur.getValue();
            int size = homes.get(curNodeNumber).size();

            if (curNodeNumber == end) {
                sb.append(curValue % MOD).append("\n");
                return;
            }

            for (int i = 0; i < size; ++i) {
                int nextNodeNumber = homes.get(curNodeNumber).get(i);
                long nextValue = homeValues[nextNodeNumber];

                if (visited[nextNodeNumber]) {
                    continue;
                }

                long updatedValue = getUpdateValue(curValue, nextValue);

                visited[nextNodeNumber] = true;
                q.offer(new Node(nextNodeNumber, updatedValue));
            }
        }
    }

    private static long getUpdateValue(long curValue, long nextValue) {
        long count = (long) Math.log10(nextValue) + 1L;
        long power = 1L;

        for (long i = 0; i < count; ++i) {
            power = (power * 10L) % MOD;
        }

        return (curValue * power + nextValue) % MOD;
    }
}