SupplyRoute.java

package com.algorithm.samsung.progress.SupplyRoute;

/**
 * @author HunSeol
 * @see https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    static int T;
    static int N;
    static String V;
    static int map[][];

    static Graph start;
    static Graph goal;

    static final int[] DY = {1, 0};
    static final int[] DX = {0, 1};

    static Queue<Graph> queue;
    static int min;

    static class Graph {
        int x;
        int y;
        int time;

        Graph(int x, int y, int time) {
            this.x = x;
            this.y = y;
            this.time = time;
        }
    }

/*
10
4
0100
1110
1011
1010
6
011001
010100
010011
101001
010101
111010
8
01333212
03121302
01220112
02003220
13323020
13010121
23120012
02322220
 */

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        T = Integer.parseInt(bf.readLine());
        for (int t = 1; t <= T; t++) {
            N = Integer.parseInt(bf.readLine());
            map = new int[N][N];
            for (int j = 0; j < map.length; j++) {
                V = bf.readLine();
                for (int k = 0; k < map[j].length; k++) {
                    map[j][k] = V.charAt(k) - 48;
                }
            }

            // Basic Setting
            start = new Graph(0, 0, 0);
            goal = new Graph(N - 1, N - 1, 0);
            min = 9999;

            // Queue Setting
            queue = new LinkedList<>();
            queue.add(start);
            while (!queue.isEmpty()) {
                Graph graph = queue.remove();
                getTime(graph);
                if (graph.x == goal.x && graph.y == goal.y) {
                    if (min > graph.time) {
                        min = graph.time;
                    }
                }
            }
            printResult(sb, t, min);
        }
        bf.close();
    }

    // 둘 중에 작은 값 선택하기.
    static void getTime(Graph graph) {
        int movedY = graph.y + DY[0];
        int movedX = graph.x + DX[1];

        if (movedY < N && graph.x < N) {
            queue.add(new Graph(graph.x, movedY, graph.time + map[movedY][graph.x]));
        }
        if (movedX < N && graph.y < N) {
            queue.add(new Graph(movedX, graph.y, graph.time + map[graph.y][movedX]));
        }
    }

    static void printResult(StringBuilder sb, int index, int result) {
        sb.setLength(0);
        sb.append("#");
        sb.append(index);
        sb.append(" ");
        sb.append(result);
        System.out.println(sb.toString());
    }
}