[SWEA] 1249. 보급로 자바(Java) 풀이

1. 문제 접근방법

    dfs, bfs로 풀 수 있는 문제입니다. 그러나 완전탐색으로 모든 지점을 방문하면 시간초과가 발생합니다. 그렇기에 조건에 부합하지 않는 경우의 수를 가지치기 해야만 합니다.

2. 문제풀이

  1. 각 좌표의 깊이를 2차원 배열인 supply에 담는다.

  2. 2차원 배열인 map을 만든 뒤, -1로 초기화한다.

  3. supply 배열을 (0, 0) 에서 시작하여 bfs를 한다. 대신 조건에 맞는 경우에만 큐에 담는다.

    3-1) 다음 가려고 하는 지점이 한번도 방문하지 않았을 경우 큐에 담는다. (if (map[nx][ny] == -1))

    3-2) 다음 가려고 하는 지점이 이미 방문했으나 그동안 지나온 깊이의 합보다 클 경우 방문한다.

         else if (map[nx][ny] > cur.sum + supply[nx][ny])

  4. (N-1, N-1)에 도착했을 경우 최소값과 비교한다.

3. 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Solution {
    public static int N;
    public static int[][] map;
    public static int[][] supply;
    public static int[] l = {-1, 1, 0, 0};
    public static int[] r = {0, 0, -1, 1};
    public static int min;
    public static Queue<loc> qu;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        for (int test_case = 1; test_case <= T; test_case++) {

            //입력
            N = Integer.parseInt(br.readLine());
            supply = new int[N + 1][N + 1];
            map = new int[N + 1][N + 1];
            qu = new LinkedList<loc>();

            min = Integer.MAX_VALUE;
            for (int i = 0; i < N; i++) {
                String[] s = br.readLine().split("");
                for (int j = 0; j < N; j++) {
                    supply[i][j] = Integer.parseInt(s[j]);
                }
            }
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    map[i][j] = -1;
                }
            }

            bfs(0, 0);
            System.out.println("#" + test_case + " " + min);
        }

        br.close();
    }

    public static void bfs(int cx, int cy) {
        qu.add(new loc(cx, cy, 0));

        while (!qu.isEmpty()) {
            loc cur = qu.poll(); // (0, 0) sum = 0
            cx = cur.x;
            cy = cur.y;

            if (cx == N - 1 && cy == N - 1) {
                if (cur.sum < min) {
                    min = cur.sum;
                }
                continue;
            }

            for (int i = 0; i < 4; i++) {
                int nx = cx + l[i];
                int ny = cy + r[i];

                if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
                    if (map[nx][ny] == -1) {
                        //지금까지 지나온 깊이의 합에 다음 가려는 지점의 깊이를 더한다.
                        qu.add(new loc(nx, ny, cur.sum + supply[nx][ny]));
                        map[nx][ny] = cur.sum + supply[nx][ny];
                    } else if (map[nx][ny] > cur.sum + supply[nx][ny]) {
                        qu.add(new loc(nx, ny, cur.sum + supply[nx][ny]));
                        map[nx][ny] = cur.sum + supply[nx][ny];
                    }
                }
            }

        }

    }
}

class loc {
    public int x;
    public int y;
    public int sum;

    loc (int x, int y, int sum) {
        this.x = x;
        this.y = y;
        this.sum = sum;
    }
}

4. 주의할점

  조건을 판단하는 map 배열을 -1이 아닌 0으로 초기화할 경우 무한루프에 빠질 수 있다.

  이 문제는 프로그래머스 - 경주로 건설 문제와 풀이가 비슷하다. 이 문제도 풀어보는 것을 추천한다.

  > https://programmers.co.kr/learn/courses/30/lessons/67259