[백준 1261] 알고스팟 - JAVA

BOJ Link

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

 

 

 

풀이 과정

최단 거리, 다익스트라, 0-1 BFS 분류로 되어있는 문제다. 나는 우선순위 큐와 가중치를 통해 풀이했다.

 

일반 BFS를 사용할 수 없는 이유

어떤 행렬에 도달할 때, 뺑 돌아오는 길이 최적해일 수 있다.

따라서 방문체크 배열을 통해 한 번 방문한 곳을 다시 방문하지 않는 로직은 적용이 불가능하다.

그러므로 모든 경로를 고려해야 하는데, 이 때 배열은 최대 100*100이므로, 모든 경우를 탐색할 순 없다.

 

핵심 아이디어

별도의 배열에 방문 여부 대신 가중치를 기록한다.

이 때, 현재 행렬 가중치 + 인접한 곳으로 가는 비용 < 인접한 곳의 가중치라면,

인접한 행렬을 갱신하고, 다음 탐색을 가중치를 정렬 기준으로 삼는 우선순위 큐에 넣는다. (큐도 가능하지만, 최적해에 가까운 탐색부터 진행해서 더 빠르다.)

 

모든 행렬은 도달할 수 있으므로, 무한루프 없이 가중치 행렬엔 해당 지점으로 도달할 수 있는 최소 비용들이 기록된다.

이후 (N-1, M-1) 지점을 출력한다.

 

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        int[] dr = {0, 0, -1, 1};
        int[] dc = {-1, 1, 0, 0};

        int[][] map = new int[N][M];
        int[][] weightMap = new int[N][M];

        for (int i = 0; i < N; i++) {
            map[i] = Arrays.stream(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();
            Arrays.fill(weightMap[i], Integer.MAX_VALUE);
        }

        PriorityQueue<int[]> q = new PriorityQueue<>(Comparator.comparingInt(o -> o[2]));
        
        weightMap[0][0] = 0;
        q.offer(new int[]{0, 0, 0});

        while (!q.isEmpty()) {
            int[] info = q.poll();
            int r = info[0];
            int c = info[1];
            int weight = info[2];

            for (int i = 0; i < 4; i++) {
                int tr = r + dr[i];
                int tc = c + dc[i];

                if (tr >= 0 && tr < N && tc >= 0 && tc < M && weight + map[tr][tc] < weightMap[tr][tc]) {
                    weightMap[tr][tc] = weight + map[tr][tc];
                    q.offer(new int[]{tr, tc, weightMap[tr][tc]});
                }
            }
        }

        System.out.println(weightMap[N - 1][M - 1]);
    }
}