[백준/JAVA] 1261번: 알고스팟

🔺 문제

1261번: 알고스팟

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
class Node implements Comparable<Node> {
    int x, y, val;
    
    public Node(int x, int y, int val) {
        this.x = x;
        this.y = y;
        this.val = val;
    }
    
    // 벽 부순 개수 기준 오름차순 정렬
    @Override
    public int compareTo(Node o) {
        return this.val - o.val;
    }
}
 
public class Main {
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};
    
    static int M, N;
    static int min = Integer.MAX_VALUE;
    
    static int[][] map;
    static boolean[][] visited;
    
    public static void main(String[] args) throws IOException {
        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];
        visited = new boolean[N + 1][M + 1];
        
        for(int i = 1 ; i <= N ; i++) {
            String str = br.readLine();
            for(int j = 1 ; j <= M ; j++) {
                map[i][j] = str.charAt(j - 1) - '0';
            }
        }
        
        System.out.println(bfs(1, 1));
    }
    
    private static int bfs(int a, int b) {
        visited[a][b] = true;
        
        // 벽 부순 개수 기준 오름차순 정렬
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(a, b, 0));
        
        while(!pq.isEmpty()) {
            Node now = pq.poll();
            
            // 도착한 경우, 종료
            if(now.x == N && now.y == M) {
                return now.val;
            }
            
            for(int d = 0 ; d < 4 ; d++) {
                int nx = now.x + dx[d];
                int ny = now.y + dy[d];
                
                if(nx < 1 || ny < 1 || nx > N || ny > M || visited[nx][ny])   continue;
                
                if(!visited[nx][ny]) {
                    visited[nx][ny] = true;
                    
                    if(map[nx][ny] == 0) {
                        pq.add(new Node(nx, ny, now.val));
                    }
                    else {
                        pq.add(new Node(nx, ny, now.val + 1)); // 벽 부순 개수 업데이트
                    }
                }
            }
        }
        
        return 0;
    }
}

✅ 해결 아이디어
✔ 다익스트라
- 일반 큐 아닌 우선순위 큐 사용

 

💥 유의사항

•  BFS를 사용하면서, 일반 큐가 아닌 우선순위 큐 사용!

  ⇨ 최단 거리가 필요한 게 아닌, 벽을 최소한으로 부수면서 가라고 했기 때문

  ⇨ 그래서 벽을 부순 개수에 대해 오름차순 정렬하면서 poll 함

 

---

🔺 다른 풀이들

- Deque를 사용하셨다.

[백준 - Java] 1261번 : 알고스팟

---

💬 느낀 점

와 다익스트라 잊고 있었는데...

다익스트라 문제들을 또 풀러 가야겠다..

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[BOJ] 백준 1261번 : 알고스팟 (JAVA)