[백준/JAVA] 14497번: 주난의 난(難)

📖 문제

14497번: 주난의 난(難)

 

 

 

💡  풀이 방식

• 다익스트라 (우선순위 큐)

 

최단 경로인 지점을 항상 우선으로 탐색하고자 점프 횟수 기준 오름차순 정렬하는 우선순위 큐를 활용한다.

class Node implements Comparable<Node> {
    int x, y, w;
    
    public Node(int x, int y, int w) {
        this.x = x;
        this.y = y;
        this.w = w;
    }
    
    @Override
    public int compareTo(Node n) {    // 💥 점프 횟수 기준 오름차순 정렬
        return this.w - n.w;
    }
}

 

 

이동하는 다음 칸의 배열 값이 1인 경우, 현재까지 걸린 점프 횟수 + 1한다.

하지만, 다음 칸의 배열의 값이 0인 경우, 현재까지 걸린 점프 횟수의 값을 그대로 가져간다.

// 💥 0이면 점프 횟수 그대로, 1이면 점프 횟수 +1
pq.add(new Node(nx, ny, map[nx][ny] == '0' ? now.w : now.w +1));

 

 

 

🔥 우선순위 큐 사용 이유

: 일반 큐를 사용한다면, 최소 점프 횟수 순이 아닌 값으로 범인에게 도달할 수 있다. (사례)

그러므로 우선순위를 고려해 추출하는 우선순위 큐를 사용해야 한다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {    
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    
    static int N,M, x1, y1, x2, y2;
    static char[][] 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() ," ");
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        map = new char[N][M];
        visited = new boolean[N][M];
        
        st = new StringTokenizer(br.readLine() ," ");
        x1 = Integer.parseInt(st.nextToken()) - 1;
        y1 = Integer.parseInt(st.nextToken()) - 1;
        x2 = Integer.parseInt(st.nextToken()) - 1;
        y2 = Integer.parseInt(st.nextToken()) - 1;
        
        for(int i = 0 ; i < N ; i++) {
            String str = br.readLine();
            for(int j = 0 ; j < M ; j++) {
                map[i][j] = str.charAt(j);
            }
        }
        
        System.out.println(dijkstra());
    }
    
    private static int dijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<>();    // 🔥 우선순위 큐 !!
        pq.add(new Node(x1, y1, 0));
        
        visited[x1][y1] = true;
        
        while(!pq.isEmpty()) {
            Node now = pq.poll();
            
            if(now.x == x2 && now.y == y2) return now.w;
            
            for(int d = 0 ; d < 4 ; d++) {
                int nx = now.x + dx[d];
                int ny = now.y + dy[d];
                
                if(nx < 0 || nx >= N || ny < 0 || ny >= M || visited[nx][ny])  continue;
                
                visited[nx][ny] = true;
                pq.add(new Node(nx, ny, map[nx][ny] == '0' ? now.w : now.w +1));    // 💥 0이면 점프 횟수 그대로, 1이면 점프 횟수 +1
            }
        }
        
        return 0;
    }
}
 
class Node implements Comparable<Node> {
    int x, y, w;
    
    public Node(int x, int y, int w) {
        this.x = x;
        this.y = y;
        this.w = w;
    }
    
    @Override
    public int compareTo(Node n) {    // 💥 점프 횟수 기준 오름차순 정렬
        return this.w - n.w;
    }
}
 

 

 

 

 

➕ 다른 풀이 방식

- 다익스트라에서 2차원 int형 배열 사용해 거리 배열에 값 저장한 풀이

백준 14497 - 주난의 난

 

- 0-1 BFS를 활용한 풀이

백준 14497번 주난의 난(難)

---

💦 어려웠던 점

- 최단 점프 횟수인 친구를 가장 먼저 처리하기 위한 처리 및 정렬하는 것을 빠뜨렸다.

- 격자 내 값이 0이냐/1이냐에 따라 점프 횟수가 바뀐다는 점을 캐치하지 못했다 (어째서!)

 

 

🧐 새로 알게 된 내용

- 우선순위 큐를 이용해 점프 횟수 기준 오름차순 정렬한 값을 뽑아와서 사용하는 것...

- 0-1 BFS : deque 을 사용해 가중치가 0인 지점은 offerFirst()하고, 1인 지점은 offerLast()한다.

 

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

---

(참고)

[Algorithm] 백준 14497 주난의 난