[백준]1261: 알고스팟 - JAVA

[백준]1261: 알고스팟

www.acmicpc.net/problem/1261

1261번: 알고스팟

풀이

단순히 최단 경로를 계산하는 문제가 아니라, 벽을 최소로 부수면서 이동하는 경로를 구하는 문제이다.

 

풀이 방법은 일반적인 BFS 풀이방법으로 풀어도 되는데, QUEUE에 들어갈 노드의 순서가 중요하다. 더 적은 벽을 부수면서 이동해야 하기 때문이다.

 

이때문에 우선순위큐를 사용하여 큐에 들어온 노드를 벽을 부순 횟수 순서대로 오름차순 정렬이 되도록 하였다. 이렇게 하면 벽을 최소로 부수면서 이동하는 최단 경로를 찾을 수 있다.

 

코드

import java.util.*;
 
public class Main {    
    
    static int n, m;
    static int[][] board;
    static boolean[][] visited;
    static int[] dx = {0, 1, 0 ,-1};
    static int[] dy = {-1, 0, 1, 0};
    
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        
        n = scan.nextInt();
        m = scan.nextInt();
        scan.nextLine();
        
        board = new int[m][n];
        for(int i = 0; i < m; i++) {
            String str = scan.nextLine();
            for(int j = 0; j < n; j++) {
                int num = Integer.valueOf(str.charAt(j)) - '0';
                board[i][j] = num;
            }
        }
        
        visited = new boolean[m][n];
        System.out.println(dijkstra());
    }
    
    public static int dijkstra() {
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.offer(new Node(0, 0, 0));
        visited[0][0] = true;
        
        while(!q.isEmpty()) {
            Node current = q.poll();
            
            if(current.x == m - 1 && current.y == n - 1) return current.wall;
                    
            for(int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];
                
                if(nx >= 0 && ny >= 0 && nx < m && ny < n && visited[nx][ny] == false) {
                    if(board[nx][ny] == 0) {
                        visited[nx][ny] = true;
                        q.offer(new Node(nx, ny, current.wall));
                    } else if(board[nx][ny] == 1) {
                        visited[nx][ny] = true;
                        q.offer(new Node(nx, ny, current.wall + 1));
                    }
                }
            }
        }
        return 0;
    }
    
    public static class Node implements Comparable<Node> {
        int x;
        int y;
        int wall;
        
        public Node(int x, int y, int wall) {
            this.x = x;
            this.y = y;
            this.wall = wall;
        }
        
        @Override
        public int compareTo(Node n) {
            return this.wall - n.wall;
        }
    }
}