[백준] 25417 고속의 숫자 탐색 - Java

 

 

 

걸어가는 경우와 뛰어가는 경우 두 가지를 모두 고려해야 한다.

 

visit을 boolean타입이 아니라 int로 설정한 후, 초기값을 -1로 초기화하고 최단거리로 가는 경우면 계속해서 갱신해주는 방식으로 풀었다.

 

visit을 boolean으로 설정하는 대신, Locate객체에 cnt변수를 추가하고 먼저 뛰어가게 한 후 걸어가는 경우를 확인하는 방식으로 bfs를 돌려도 해결할 수 있을 것 같다.

 

중간에 cur.r 대신 r으로 바꿔써서 시간낭비가 있었다.

 

 

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

public class Main {

    static int[][] map = new int[5][5];    
    static int[] dr = {-1,1,0,0};
    static int[] dc = {0,0,-1,1};

    static int destinationR = 0;
    static int destinationC = 0;

    static int[][] visit = new int[5][5];

    static int r, c;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for(int i=0; i<5; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<5; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 1){
                    destinationR = i;
                    destinationC = j;
                }
                visit[i][j] = -1;
            }
        }

        StringTokenizer st = new StringTokenizer(br.readLine());

        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());        

        Queue<Locate> q = new LinkedList<>();

        q.add(new Locate(r,c));

        int ans = Integer.MAX_VALUE;
     
        visit[r][c] = 0;
        
        while(!q.isEmpty()){
            Locate cur = q.poll();         
            
            if(cur.r == destinationR && cur.c == destinationC){
                ans = Math.min(ans, visit[cur.r][cur.c]);
            }

            for(int i=0; i<4; i++){ // 먼저 뛰어가게 해야됨    
                int nextR = cur.r;
                int nextC = cur.c;   

                while(true){
                    nextR += dr[i];
                    nextC += dc[i];
                    
                    if(nextR >= 5 || nextR <= -1 || nextC >= 5 || nextC <= -1){
                        nextR -= dr[i];
                        nextC -= dc[i];
                        break;
                    } 
                    
                    if(map[nextR][nextC] == -1){
                        nextR -= dr[i];
                        nextC -= dc[i];
                        break;
                    }

                    if(map[nextR][nextC] == 7){
                        break;
                    }
                }

                if(r == nextR && c == nextC){
                    continue;
                }

                if(visit[nextR][nextC] == -1){
                    visit[nextR][nextC] = visit[cur.r][cur.c] + 1;
                    q.add(new Locate(nextR, nextC));
                }else{
                    if(visit[nextR][nextC] > visit[cur.r][cur.c] + 1){
                        visit[nextR][nextC] = visit[cur.r][cur.c] + 1;
                        q.add(new Locate(nextR, nextC));
                    }
                }
                
            }

            for(int i=0; i<4; i++){
                int nextR = cur.r + dr[i];
                int nextC = cur.c + dc[i];

                if(nextR >= 5 || nextR <= -1 || nextC >= 5 || nextC <= -1){
                    continue;
                }  

                if(map[nextR][nextC] == -1){
                    continue;
                }

                if(visit[nextR][nextC] == -1){
                    visit[nextR][nextC] = visit[cur.r][cur.c] + 1;
                    q.add(new Locate(nextR, nextC));
                }else{
                    if(visit[nextR][nextC] > visit[cur.r][cur.c] + 1){
                        visit[nextR][nextC] = visit[cur.r][cur.c] + 1;
                        q.add(new Locate(nextR, nextC));
                    }
                }
            }

        }     

        System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
        
    }
}

class Locate{
    int r,c;
    int cnt = 0;
    Locate(int r, int c){
        this.r = r;
        this.c = c;        
    }
}