[BaekJoon] 24955 숫자 이어 붙이기 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/24955

2.  문제

요약

• 철수는 수를 이어 붙이는 놀이를 좋아하는데, 같은 두 수를 이어 붙이더라도 이어 붙이는 순서에 따라 값이 달라집니다.
• 철수가 살고 있는 마을에는 집이 여러 채 있고, 각 집에는 1부터 N까지 번호가 붙어있습니다.
• 두 집 사이에 존재하는 총 N - 1개의 도로를 통해 서로 이동할 수 있습니다.
• $i$번째 도로는 $a_i$번 집과 $b_i$번 집을 잇습니다.
• 집과 도로는 트리의 형태를 이룹니다. 즉, 어떤 집에서 시작해서 몇 개의 도로를 거쳐 어떤 집이라도 갈 수 있고, 같은 집을 두 번 방문하지 않을 경우 그 경로는 유일합니다.
• 철수는 총 Q번 수를 이어 붙이는 놀이를 할 것입니다.
• $i$번째 놀이에서는 $x_i$번째 집에서 시작해서 $y_i$번째 집까지 이동하면서, 이동하는 경로 상에 있는 집들의 대문에 쓰여있는 수들을 방문하는 순서대로 이어 붙일 것입니다.
• 만약 $x_i = y_i$라면, $x_i$번째 집의 대문에 쓰인 수가 답이 될 것입니다.
• $i$번째 놀이가 끝났을 때 이어 붙인 수의 값을 1,000,000,007로 나눈 나머지를 구하는 문제입니다.
• 입력: 첫 번째 줄에 2보다 크거나 같고 1,000보다 작거나 같은 집의 개수 N과 1보다 크거나 같고 1,000보다 작거나 같은 철수가 놀이를 할 횟수 Q가 주어지고 두 번째 줄에 N개의 집의 대문에 쓰여있는 수 $A_i$가 순서대로 주어집니다. 세 번째 줄부터 N - 1개의 줄에 도로의 정보가 주어지는데, 2 + $i$번째 줄에는 $i$번째 도로가 잇는 두 집의 번호 $a_i, b_i$에 대한 정보가 주어집니다. 그 다음 줄에는 로봇의 출발 지점의 위치(행과 열의 번호)와 바라보는 방향이 주어집니다. N + 2번째 줄부터 N + Q + 1번째 줄까지는 놀이에 대한 정보가 주어집니다. N + $i$ + 1번째 줄에는 $i$번째 놀이를 시작할 집의 번호 $x_i$와 끝낼 집의 번호 $y_i$가 주어집니다.
• 출력: 첫 번째 줄부터 Q번째 줄에 걸쳐, $i$번째 줄에는 $i$번째 놀이의 결과를 1,000,000,007로 나눈 나머지를 출력합니다.

3.  소스코드

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

public class Main {
    static final String DIVIDER = "1000000007";
    static int N, Q;
    static String[] A;
    static HashMap<Integer, ArrayList<Integer>> map;
    static int[][] plays;
    static void input() {
        Reader scanner = new Reader();
        N = scanner.nextInt();
        Q = scanner.nextInt();
        A = new String[N + 1];
        map = new HashMap<>();
        plays = new int[Q][2];
        for(int house = 1; house <= N; house++) {
            map.put(house, new ArrayList<>());
            A[house] = scanner.next();
        }
        for(int edge = 0; edge < N - 1; edge++) {
            int h1 = scanner.nextInt(), h2 = scanner.nextInt();
            map.get(h1).add(h2);
            map.get(h2).add(h1);
        }
        for(int idx = 0; idx < Q; idx++) {
            plays[idx][0] = scanner.nextInt();
            plays[idx][1] = scanner.nextInt();
        }
    }

    static void solution() {
        StringBuilder sb = new StringBuilder();
        for(int idx = 0; idx < Q; idx++) {
            String answer = bfs(plays[idx][0], plays[idx][1]);
            BigInteger ans = new BigInteger(answer);
            BigInteger remainder = ans.remainder(new BigInteger(DIVIDER));
            sb.append(remainder).append('\n');
        }
        System.out.print(sb);
    }

    static String bfs(int start, int end) {
        Queue<Number> queue = new LinkedList<>();
        boolean[] visited = new boolean[N + 1];
        visited[start] = true;
        queue.offer(new Number(start, A[start]));
        String answer = "0";
        while(!queue.isEmpty()) {
            Number cur = queue.poll();
            if(cur.house == end) {
                if(answer.compareTo(cur.number) < 0) {
                    answer = cur.number;
                }
            }
            for(int neighbor : map.get(cur.house)) {
                if(!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(new Number(neighbor, cur.number + A[neighbor]));
                }
            }
        }
        return answer;
    }

    static class Number {
        int house;
        String number;
        public Number(int house, String number) {
            this.house = house;
            this.number = number;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 각 집에 적혀있는 수들을 이어 붙인 수를 표현하기 위해 Number 클래스를 생성합니다.
  • 이 클래스는 집의 번호 house, 현재까지 이어 붙인 수 number를 멤버로 갖습니다.
• 각 놀이에 대해 시작할 집의 번호부터 끝낼 집의 번호까지 BFS 탐색을 진행하여 그 중 가장 큰 수를 찾습니다.
  • Queue를 생성하고 시작할 집의 번호와 시작할 집에 적혀있는 수를 Number 객체로 생성하여 Queue에 넣습니다.
  • 각 집에 대해 방문 체크를 하기 위해 visited 배열을 생성하고 시작할 집의 번호에 대해서는 방문 체크를 진행합니다.
  • Queue가 비워질 때까지 Number 객체를 하나씩 뽑아 번호를 이어 붙입니다.
    • 만약 Queue에서 뽑은 Number 객체의 house 값이 끝낼 집의 번호와 같다면 이어 붙인 수의 값을 갱신합니다. 만약 이전까지 이어 붙인 수보다 Queue에서 뽑은 Number 객체의 number 값이 더 크다면 해당 값으로 갱신합니다.
    • 그렇지 않다면 해당 집의 이웃하는 집들을 확인하여 아직 이웃하는 집을 방문하지 않았다면 Queue에서 뽑은 Number 객체의 number 뒤에 이웃하는 집에 적혀있는 수를 이어 붙인 수를 구해 Number 객체로 만들어 Queue에 넣고 이웃하는 집에 대해 방문 체크를 진행합니다.
  • 각 놀이에 대해 BFS를 통하여 가장 큰 수를 찾았다면 이를 1,000,000,007로 나눈 나머지를 구합니다.
    • 이어 붙인 수의 길이는 long 범위를 넘어설 수 있기 때문에 BigInteger를 이용하여 계산합니다.