BOJ#2412 암벽 등반

BOJ#2412 암벽 등반

* 문제

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

* 풀이

BFS를 통해 암벽 정상까지 최소 이동 횟수를 구하면 됩니다.

- 일단 Start 노드를 시작으로 인접한 노드들을 탐색하고 조건에 맞는 노드들만 다시 Queue에 넣어줍니다.

- 조건 :  |a-x| <= 2 && |b-y| <=2 && 방문하지 않은 정점

- 암벽의 정상에 도달할때까지 반복

사실 해답을 구하는 것에 대해서는 일반적인 BFS 기초문제와 다를 것이 없습니다만,

n, x, y 입력 조건이 상당히 크게 잡혀 있으므로 별도로 탐색의 범위를 줄여주는 작업을 추가했습니다.

일단 입력받은 홈(노드)들을 오름차순으로 정렬하였고 (소스에서 Comparator 부분)

현재 검사 노드의 인접한 노드들을 탐색하는 과정에서

현재 검사 노드의 좌표가 (x, y) 일 때

 (x좌표 -2, y좌표 -2) 에 해당되는 노드들부터 탐색을 시작할 수 있도록 하였고

마찬가지로 인접한 노드의 좌표가 y좌표 + 2가 넘어가면 바로 break하여 탐색을 줄일 수 있도록 하였습니다. (소스에서 binarySeach 부분)

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/master/BOJ%232412/src/Main.java

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

public class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int T = Integer.parseInt(st.nextToken());

        Node[] nodes = new Node[n];
        boolean[] discovered = new boolean[n];

        for (int i = 0; i < n; i++) {

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

            nodes[i] = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        Arrays.sort(nodes);

        Comparator<Node> cp = (o1, o2) -> {

            if (o1.col < o2.col) return -1;
            if (o1.col > o2.col) return 1;
            if (o1.col == o2.col) {

                if (o1.row < o2.row) return -1;
                if (o1.row > o2.row) return 1;
            }

            return 0;
        };

        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(0, 0));

        int step = -1;

        while (!queue.isEmpty()) {

            step++;

            int size = queue.size();
            for (int i = 0; i < size; i++) {

                Node u = queue.poll();

                if (u.col == T) {

                    System.out.println(step);
                    return;
                }

                // 탐색의 범위를 줄여보자
                int startIdx = Arrays.binarySearch(nodes, new Node(u.row - 2 < 0 ? 0 : u.row - 2, u.col - 2 < 0 ? 0 : u.col - 2), cp);
                startIdx = startIdx < 0 ? -startIdx - 1 : startIdx;

                // 탐색
                for (int j = startIdx; j < n; j++) {

                    int nextRow = nodes[j].row;
                    int nextCol = nodes[j].col;

                    // 체크할 조건들
                    if (discovered[j]) continue;
                    if (Math.abs(u.row - nextRow) > 2) continue;
                    if (u.col - nextCol < -2) break; // 탐색의 범위를 줄여보자
                    if (u.col - nextCol > 2) continue;

                    queue.add(new Node(nextRow, nextCol));
                    discovered[j] = true;
                }
            }
        }

        System.out.println(-1);
    }
}

class Node implements Comparable<Node> {

    int row, col;

    Node(int row, int col) {

        this.row = row;
        this.col = col;
    }

    @Override
    public int compareTo(Node o) {

        return this.col < o.col ? -1 : this.col > o.col ? 1 : this.row < o.row ? -1 : 1;
    }

    @Override
    public String toString() {

        return "(" + row + ", " + col + ")\n";
    }
}