[백준 1261] 알고스팟 (Java, 다익스트라)

[백준 1261] 알고스팟

문제 출처 : 링크

경로를 이동하는 걸 생각하면 DFS나 BFS를 활용해야 될 것 같다.

하지만 기존의 문제와는 다르게, '가중치'가 존재한다. 

1인 값을 가지고 있는 곳을 지날 때는 벽이 있는 것이므로 부수고 지나갈 수 밖에 없다. 따라서 그냥 움직이는 것이 아닌, 1인 곳을 지나갈 때마다 값을 변경시켜나가야 하는 문제다.

우선 미로탐색처럼 BFS와 유사한 방식으로 나아가지만, 이 가중치 값을 최소화 시키기 위해 그냥 큐가 아닌 우선순위 큐를 사용해서 저장한다. (우선순위를 위해 comperable 활용)

class Spot implements Comparable<Spot>{
    int y;
    int x;
    int cost;
    
    public Spot(int y, int x, int cost) {
        this.y = y;
        this.x = x;
        this.cost = cost;
    }
 
    @Override
    public int compareTo(Spot o) {
        return this.cost < o.cost ? -1 : 1;
    }
    
    
}

이처럼 시작 점에서 도착 점까지의 가중치가 가장 낮은 최단거리를 구할 때 사용하는 것이 '다익스트라 알고리즘'이다. (java를 활용한 기본적인 다익스트라 코드)

input으로 입력받는 벽의 유무를 2차원 행렬 map에 저장하고

거리 값을 저장할 2차원 행렬 dist를 따로 만들어준다. (기존의 visited와는 약간 다른 방식)

동서남북으로 움직이면서, 이전 지역의 거리 값과 옮긴 지역의 map값(벽의 유무:0,1)을 더한 값을 저장한다. 이때 값 비교를 위해 기존의 dist배열은 초기값을 무한대 값으로 주자

//거리값에 무한대 값 저장
for (int i = 0; i < dist.length; i++) {
    for (int j = 0; j < dist[i].length; j++) {
        dist[i][j] = Integer.MAX_VALUE;
    }
}
 
//맵에 input 저장 (1부터 N,M까지)
for (int y = 1; y < map.length; y++) {
    String[] str = br.readLine().split("");
    for (int x = 1; x < map[y].length; x++) {
        map[y][x] = Integer.parseInt(str[x-1]);
    }
}

결국 마지막 위치까지 도달하게 되면, 해당 위치의 dist 배열 값을 출력하면 답을 구할 수 있다.

다익스트라는 이처럼 시작과 끝이 주어져있을 때 가중치 값에 대한 최단 경로를 구할 때 사용하면 효율적이다. (음수가 나오는 경우는 다른 알고리즘을 사용해야 함)

전체 소스 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
class Spot implements Comparable<Spot>{
    int y;
    int x;
    int cost;
    
    public Spot(int y, int x, int cost) {
        this.y = y;
        this.x = x;
        this.cost = cost;
    }
 
    @Override
    public int compareTo(Spot o) {
        return this.cost < o.cost ? -1 : 1;
    }
    
    
}
 
public class Problem1261 {
 
    static int N;
    static int M;
    static int[][] map;
    static int[][] dist;
    static PriorityQueue<Spot> pq;
    
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};
    static int result = 0;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        M = Integer.parseInt(st.nextToken()); // 행
        N = Integer.parseInt(st.nextToken()); // 열
        
        map = new int[N+1][M+1];
        dist = new int[N+1][M+1];
        
        
        //거리값에 무한대 값 저장
        for (int i = 0; i < dist.length; i++) {
            for (int j = 0; j < dist[i].length; j++) {
                dist[i][j] = Integer.MAX_VALUE;
            }
        }
        
        //맵에 input 저장 (1부터 N,M까지)
        for (int y = 1; y < map.length; y++) {
            String[] str = br.readLine().split("");
            for (int x = 1; x < map[y].length; x++) {
                map[y][x] = Integer.parseInt(str[x-1]);
            }
        }
        
        
        //우선순위 큐 생성
        pq = new PriorityQueue<>();
        
        bfs();
        
        
        System.out.println(result);
    }
    
    public static void bfs(){
        
        //첫번째 시작 값 add
        pq.add(new Spot(1, 1, 0));
        dist[1][1] = 0;
        
        while(!pq.isEmpty()){
            
            Spot s = pq.poll();
            
            
            //끝까지 도착하면 가중치 값 가지고 return
            if(s.y == N && s.x == M){
                result = s.cost;
                return;
            }
            
            
            for (int i = 0; i < 4; i++) {
                int ny = s.y + dy[i];
                int nx = s.x + dx[i];
                
                if(ny>0 && nx>0 && ny<=N && nx<=M){ // 1 ~ N,M일때만
                    
                    if(dist[ny][nx] > dist[s.y][s.x] + map[ny][nx]){
                        dist[ny][nx] = dist[s.y][s.x] + map[ny][nx];
                        pq.add(new Spot(ny, nx, dist[ny][nx]));
                    }
                    
                }
            }
        }
    }
    
    
}