[백준 2412] 암벽 등반 (JAVA)

문제

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

풀이

BFS로 해결할 수 있습니다. x의 범위가 1000000 이하이고 y의 범위가 200000 이하이기 때문에 배열로 방문처리하는 건 메모리 초과를 발생시킵니다. y축 기준으로 x축들을 List 형태로 저장하고 방문한 암벽들은 바로바로 제거하시면 방문처리 대신 사용할 수 있습니다.
(현재 방문한 암벽은 가장 빠르게 접근했기 때문에 그 이후에는 접근할 필요가 없습니다.)

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int n, T;
    static ArrayList<Integer>[] rock;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            rock[y].add(x);
        }

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

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

    public static int bfs() {

        Queue<Loc> q = new LinkedList<>();
        q.offer(new Loc(0, 0));

        int move = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int s = 0; s < size; s++) {
                Loc loc = q.poll();
                if (loc.y == T) return move;
                for (int y = loc.y - 2; y <= loc.y + 2; y++) {
                    if (y < 0 || y >= 200001) continue;
                    for (int j = 0; j < rock[y].size(); j++) {
                        int x = rock[y].get(j);
                        if (loc.x + 2 < x) break;
                        else if (loc.x - 2 > x) continue;

                        rock[y].remove(j);
                        q.add(new Loc(x, y));
                        j--;
                    }
                }
            }
            move++;
        }

        return -1;
    }

    public static class Loc {
        int x, y;

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