[백준] 암벽 등반 2412 java -bfs

(0,0)에서 시작해 y==3인 경우까지 가는 최단 거리를 구하는 문제로

이해할 수 있으므로 bfs로 풀 수 있다

하지만 범위가 크기  때문에 기본 이차원배열로 방문처리를 하면 시간초과가 발생한다

따라서 ArrayList<Integer>[]에 값을 저장한 후에

방문한 경우에 remove로 배열 값을 바로 바로 삭제해주는 식으로 방문처리를 해줘야 한다

여기서 주의할 점은 삭제한 경우에 Index 크기가 1씩 줄어들기 때문에 -1을 해주어야 한다!

 

 

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

 

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

public class Main {
    static ArrayList<Integer>[] map;
    static int n, T;
    static int bfs(){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0,0,0});

        map[0].remove(0);

        while(!q.isEmpty()){
            int[] now = q.poll();
            int nowX = now[0];
            int nowY = now[1];
            int cnt = now[2];

            if(nowX==T){
                return cnt;
            }

            for(int i=0;i<=T;i++){
                if(map[i]!=null){
                    for(int j=0;j<map[i].size();j++){
                        int nextX = i;
                        int nextY = j; //index
                        int absX = Math.abs(nowX-nextX);
                        int absY = Math.abs(nowY-map[nextX].get(nextY));
                        if(absX<=2 && absY<=2){
                            q.add(new int[]{nextX, map[nextX].get(nextY),cnt+1});
                            map[nextX].remove(nextY);
                            j--;
                        }
                    }
                }
            }
        }
        return -1;
    }

    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());
        T = Integer.parseInt(st.nextToken());

        map = new ArrayList[T+1];

        for(int i=0;i<=T;i++){
            map[i] = new ArrayList<>();
        }

        map[0].add(0);

        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            int value = Integer.parseInt(st.nextToken());
            int key = Integer.parseInt(st.nextToken());

            map[key].add(value);
        }

        for(int i=0;i<=T;i++){
            Collections.sort(map[i]);
        }

        System.out.println(bfs());
    }

}