[BOJ] 백준 [16930] 달리기 JAVA

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

16930번: 달리기

문제

풀이

이 문제에서 내가 집은 포인트는 3 가지이다.

1. 우선 순위 큐를 이용하여 최대한 시간이 덜 걸리는 순으로 처리하는 것 (우선순위큐 bfs 다익스트라 이용)

2. dp배열을 이용해서 이미 왔던 곳이면 break를 거는 것

3. 이중 for 문을 이용해서 nextX,nextY를 정할 때 , 1부터~k까지 이동가능한 모든 경우를 큐에 넣는 것

 

import java.util.*;
import java.io.*;
 
public class Main{
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    static int[][] dp;
    static int h,w,k;
    static Point start,end;
    static Queue<Point> queue;
    static char[][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        h = Integer.parseInt(input[0]); w = Integer.parseInt(input[1]); k = Integer.parseInt(input[2]);
        map = new char[h+1][w+1];
        dp = new int[h+1][w+1];
        for(int i=1;i<=h;i++){
            char[] ch = br.readLine().toCharArray();
            for(int j=1;j<=w;j++) {
                map[i][j] = ch[j - 1];
                dp[i][j] = 987654321;
            }
        }
        input = br.readLine().split(" ");
        start = new Point(Integer.parseInt(input[1]),Integer.parseInt(input[0]),0);
        end = new Point(Integer.parseInt(input[3]),Integer.parseInt(input[2]),0);
        queue = new PriorityQueue<>();
        dp[start.y][start.x] = 0;
        queue.add(start);
 
        while(!queue.isEmpty()){
            Point tmp = queue.poll();
            if(end.isSame(tmp)){
                System.out.println(tmp.cnt);
                return;
            }
            for(int i=0;i<dx.length;i++){
                for(int j=1;j<=k;j++){
                    int nextX = tmp.x + dx[i]*j;
                    int nextY = tmp.y + dy[i]*j;
 
                    if(!isRange(nextX,nextY)) // 범위를 벗어나면 다른 방향으로 탐색
                        continue;
                    if(map[nextY][nextX]=='#' ||  dp[nextY][nextX] < dp[tmp.y][tmp.x]+1){
                            break; // 벽이거나 dp 카운트가 기존에 있던자리가 더 낮으면
                    }
                    if(dp[nextY][nextX] == 987654321){
                        dp[nextY][nextX] = tmp.cnt+1;
                        queue.add(new Point(nextX,nextY,tmp.cnt+1));
                    }
                }
            }
        }
        System.out.println(-1);
    }
    static boolean isRange(int x,int y){
        return x>0&&y>0&&x<=w&&y<=h;
    }
}
class Point implements Comparable<Point>{
    int x;
    int y;
    int cnt;
    public Point(int x, int y,int cnt) {
        this.x = x;
        this.y = y;
        this.cnt=cnt;
    }
    public boolean isSame(Point o){
        return this.x==o.x && this.y == o.y;
    }
    @Override
    public int compareTo(Point o) {
        return this.cnt-o.cnt;
    }
}
 

 생각보다 생각할 것이 많았던 문제였다.