[BOJ1261] 알고스팟 (최단 경로, 다익스트라)

 

 

---

문제 링크 

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

1261번: 알고스팟

 

문제 풀이 

- 다익스트라 카테고리 분류되어 있어 다익스트라 알고리즘 방식으로 풀었다 

- (1,1) -> (N, M) 까지 벽을 최소로 부숴야 하므로 우선 순위 큐를 사용 (부숴버린 벽돌 수에 대해 오름차순 정렬)

 

 

제출 코드 

import java.util.*;
import java.io.*;

public class Main {
    
    static int n, m;
    static int[][] board;

    static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static void input() 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()); // 세로 (행)

        board = new int[n + 1][m + 1];
        for(int i = 1; i <= n; i++) {
            String line = br.readLine();
            for(int j = 1; j <= m; j++) {
                board[i][j] = line.charAt(j - 1) - '0'; // char to int
            }
        }
    }

    static class Node implements Comparable<Node> {
        int i;
        int j;
        int count;

        public Node(int i, int j, int count) {
            this.i = i;
            this.j = j;
            this.count = count;
        }

        @Override
        public int compareTo(Node other) {
            return count - other.count; // 오름차순
        }
    }

	// (1, 1)-> (n , m) 도착
    static void dijkstra() {
        Queue<Node> que = new PriorityQueue<>();
        que.add(new Node(1, 1, 0));

        boolean[][] visit = new boolean[n + 1][m + 1];
        visit[1][1] = true;

        int result = Integer.MAX_VALUE;
        while(!que.isEmpty()) {
            Node cur = que.poll();

            if(cur.i == n && cur.j == m) {
                result = Math.min(result, cur.count);
                continue;
            }

            for(int i = 0; i < 4; i++) {
                int di = cur.i + dir[i][0];
                int dj = cur.j + dir[i][1];
                int count = cur.count; // 현재까지 부순 벽돌 수

                if(di < 1 || dj < 1 || di > n || dj > m) continue;
                if(visit[di][dj]) continue;
                if(board[di][dj] == 1) count += 1;

                visit[di][dj] = true;
                que.add(new Node(di, dj, count));
            }
        }

        System.out.println(result);
    }

    static void pro() {
        dijkstra();
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}