백준 16930번 달리기 (JAVA)

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

16930번: 달리기

 

저는 해당 문제를 DP와 BFS를 이용해 문제를 해결하였습니다.

처음에는 boolean으로 방문체크를 함으로써 96퍼센트에서 시간초과가 나왔습니다.

다음으로는 DP를 이용해 해당 노드에 어떤 최소 시간때에 도착하였는지를 확인하였고, 만약 이 노드가 현재시간보다 +1보다 크다면 break해 해당 방향 탐색을 종료해 시간을 단축시켰습니다.

 

 

 

package BOJ.BFS;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_16930 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(st.nextToken());
        int m = stoi.apply(st.nextToken());
        int k = stoi.apply(st.nextToken());
        char[][] map = new char[n][m];
        for(int i = 0 ; i < n ; i++){
            String command = br.readLine();
            for(int j = 0 ; j < m ; j++){
                map[i][j] = command.charAt(j);
            }
        }
        st = new StringTokenizer(br.readLine()," ");
        int startY = stoi.apply(st.nextToken()) - 1;
        int startX = stoi.apply(st.nextToken()) - 1;
        int endY = stoi.apply(st.nextToken()) - 1;
        int endX = stoi.apply(st.nextToken()) - 1;
        System.out.println(bfs(map,n,m,k,startY,startX,endY,endX));
    }
    private static class Node implements Comparable<Node> {
        int y;
        int x;
        int cnt;

        public Node(int y, int x, int cnt) {
            this.y = y;
            this.x = x;
            this.cnt = cnt;
        }

        @Override
        public int compareTo(Node o) {
            return this.cnt - o.cnt;
        }
    }
    private static int bfs(char[][] map, int n ,int m , int k, int startY, int startX, int endY, int endX) {
        final int dy[] = {-1,0,1,0};
        final int dx[] = {0,1,0,-1};
        final int INF = 987654321;
        Queue<Node> q = new PriorityQueue<>();
        int[][] dp = new int[n][m];
        for(int i = 0 ; i < n ; i++){
            Arrays.fill(dp[i],INF);
        }
        q.offer(new Node(startY,startX,0));
        while(!q.isEmpty()){
            Node now = q.poll();
            if(now.y == endY && now.x == endX){
                return now.cnt;
            }
            for(int i = 0 ; i < 4; i++){
                int ny = now.y;
                int nx = now.x;
                for(int j = 1 ; j <= k ; j++){
                    ny += dy[i];
                    nx += dx[i];
                    if(ny >= 0 && ny < n && nx >= 0 && nx < m){
                        if(map[ny][nx] == '#' || dp[ny][nx] < now.cnt +1){
                            break;
                        }
                        if(dp[ny][nx] == INF){
                            dp[ny][nx] = now.cnt + 1;
                            q.offer(new Node(ny,nx,now.cnt + 1));
                        }
                    }
                }
            }
        }
        return -1;
    }
}