[백준] 2412. 암벽 등반(Java)

문제

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

 

풀이

시작 위치에서 종료 위치까지 도달하기 위해 그래프 탐색을 이용해서 문제를 해결했습니다.

해당 문제는 2차원 배열에 위치를 마킹하거나 방문처리를 하게되면 메모리 초과가 발생합니다.
따라서 그래프 탐색을 위해 입력받은 값을 y(열)를 기준으로 list 배열에 x(행)값을 저장해두었고
현재 행에서 갈 수 있는 열에 대해서, 다음으로 갈 수 있는 유효한 좌표를 탐색했습니다.

최단거리를 구해주는 문제이기 때문에
T열에 가장 먼저 도달했을 때의 cnt 값을 리턴해주었습니다.(도달하지 못했다면 -1 리턴)

 

코드

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

public class Main {
    static int N, T;
    static List<Integer>[] list;
    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());

        list = new ArrayList[T + 1];
        for (int i = 0; i <= T; i++)
            list[i] = new ArrayList<>();

        boolean isGame = false;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            if (c == T) isGame = true;

            list[c].add(r);
        }

        if (!isGame) System.out.print(-1);
        else System.out.print(bfs());
    }

    private static int bfs() {
        Queue<Node> q = new ArrayDeque<>();
        q.offer(new Node(0, 0));

        List<Integer> next;
        int cnt = 0;

        while (!q.isEmpty()) {
            int qSize = q.size();

            for (int i = 0; i < qSize; i++) {
                Node cur = q.poll();
                int r = cur.r;
                int c = cur.c;

                if (c == T) return cnt;

                for (int nc = c - 2; nc <= c + 2; nc++) {
                    if (!isValid(nc)) continue;

                    next = list[nc];

                    for (int j = 0; j < next.size(); j++) {
                        int nr = next.get(j);
                        if (Math.abs(nr - r) > 2) continue;

                        next.remove(j);
                        q.add(new Node(nr, nc));
                        j--;
                    }
                }
            }

            cnt ++;
        }

        return -1;
    }

    private static boolean isValid(int nc) {
        return nc >= 0 && nc <= T;
    }

    static class Node{
        int r, c;

        public Node(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}