[코딩테스트] SWEA 1249 보급로(Java)

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
SWEA 1249 보급로입니다.

포인트

문제가 여러 조건이 많은 것 같지만 배열의 숫자는 이동비용이라고 가정하면
결국 출발지로부터 도착지까지의 최소 비용을 구하는 문제입니다.

따라서 BFS로 문제를 풀면 가능합니다. BFS는 한 위치에 도달하기에 최소 경로가 보장되기 때문에
step이라는 배열을 통해 비용을 저장합니다.

소스코드

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

public class Q1249 {
    static class Pair {
        int x, y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    private static int testCase, N;
    private static int[][] map;
    private static boolean[][] visited;
    private static int[][] step;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        testCase = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int t = 1; t <= testCase; t++) {
            N = Integer.parseInt(br.readLine());
            map = new int[N][N];
            visited = new boolean[N][N];
            step = new int[N][N];

            for (int i = 0; i < N; i++) {
                String line = br.readLine();
                Arrays.fill(step[i], Integer.MAX_VALUE);
                for (int j = 0; j < N; j++) {
                    map[i][j] = line.charAt(j) - '0';
                }
            }

            bfs();

            sb.append("#").append(t).append(" ").append(step[N - 1][N - 1]);
            if (t != testCase) {
                sb.append("\n");
            }
        }
        System.out.println(sb);
    }

    private static void bfs() {
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(0, 0));
        step[0][0] = 0;
        visited[0][0] = true;

        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        while (!q.isEmpty()) {
            Pair cur = q.poll();

            for (int idx = 0; idx < 4; idx++) {
                int nextX = cur.x + dx[idx];
                int nextY = cur.y + dy[idx];

                if (canGo(cur.x, cur.y, nextX, nextY)) {
                    step[nextX][nextY] = step[cur.x][cur.y] + map[nextX][nextY];
                    visited[nextX][nextY] = true;
                    q.add(new Pair(nextX, nextY));
                }
            }
        }
    }

    private static boolean canGo(int prevX, int prevY, int x, int y) {
        if(!inRange(x, y)) return false;
        if(step[x][y] <= step[prevX][prevY] + map[x][y]) return false;

        return true;
    }

    private static boolean inRange(int x, int y) {
        return 0 <= x && x < N && 0 <= y && y < N;
    }
}
/*
2
4
0100
1110
1011
1010
6
011001
010100
010011
101001
010101
111010
 */

코드 설명

• inRange(int x, int y)
  x, y가 격자 내에 있는지 판단하는 함수
  • ROW와 COL을 기준으로 좌표가 16×16 격자 안에 있는지 확인합니다.

• canGo(int x, int y)
  다음 칸을 갈 수 있는지 판단
  • 격자 범위를 벗어나지 않았고
  • 현재의 비용이 이미 저장된 비용보다 더 적은 경로라면
  • true를 반환
• bfs() 함수
  
  • BFS 큐를 통해 너비 우선 탐색을 수행합니다.
  • 다음 위치 (nx, ny)가 갈 수 있는 위치이면 큐에 추가하고 방문 처리합니다