[JAVA/자바][백준 2412] 암벽 등반

문제

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

접근 방법

이분 탐색 문제집을 따라 풀던 중 만난 문제다. '알고리즘 분류' 란에 이분 탐색과 너비 우선 탐색이 있어 두 가지의 풀이가 존재한다고 생각했다. 그러나, 이분 탐색 방식으로 해결하지 못했다. 너비 우선 탐색을 사용하되, 다음 방문 노드를 찾을 때 이분 탐색을 이용하는 문제로 이해했다.

(이 풀이는 이분탐색을 제대로 이용하지 못했다)

풀이

1. (0,0) 을 포함한 n + 1개 홈의 좌표를 저장할 Node[] graph 초기화
2. n + 1개의 홈에 대한 방문 횟수를 저장할 int[] visited 초기화
3. graph 배열을 정렬한다 (y를 기준으로 오름차순, 이후 동일한 y에 대해 x를 기준으로 오름차순)
4. BFS 알고리즘 적용 (기준 인덱스의 우측과 좌측, 두 방향을 탐색한다)

• 조건 적용하면서 우측 탐색
  • 오른쪽 인덱스의 y >= 현재 인덱스의 y
    • y + 2 보다 큰 값이 처음 등장하면 이후의 값들은 탐색하지 않아도 된다.
• 조건 적용하면서 좌측 탐색
  • 왼쪽 인덱스의 y <= 현재 인덱스의 y
    • y - 2 보다 작은 값이 처음 등장하면 이후의 값들은 탐색하지 않아도 된다.

코드

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

public class Main {
    static class Node {
        int x;
        int y;

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

    private static Node[] graph;
    private static int[] visited;
    private static int n, T;

    public static void main(String[] args) throws IOException, NumberFormatException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());
        graph = new Node[n + 1];
        visited = new int[n + 1];
        graph[0] = new Node(0, 0);
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            graph[i] = new Node(x, y);
        }

        Arrays.sort(graph, (o1, o2) -> {
            if (o1.y > o2.y) {
                return 1;
            } else if (o1.y == o2.y) {
                if (o1.x > o2.x) {
                    return 1;
                }
            }
            return -1;
        });

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

    private static int BFS() {
        Queue<Integer> q = new LinkedList<>();
        q.add(0);
        visited[0] = 0;

        while (!q.isEmpty()) {
            int nowIndex = q.poll();
            if (graph[nowIndex].y == T) {
                return visited[nowIndex];
            }
            int nowX = graph[nowIndex].x;
            int nowY = graph[nowIndex].y;

            for (int nextIndex = nowIndex + 1; nextIndex <= n; nextIndex++) {
                if (visited[nextIndex] != 0) {
                    continue;
                }
                int nextX = graph[nextIndex].x;
                int nextY = graph[nextIndex].y;
                if (nextY - nowY > 2) {
                    break;
                }
                if (Math.abs(nextX - nowX) > 2) {
                    continue;
                }
                visited[nextIndex] = visited[nowIndex] + 1;
                q.add(nextIndex);
            }
            for (int nextIndex = nowIndex - 1; nextIndex > 0; nextIndex--) {
                if (visited[nextIndex] != 0) {
                    continue;
                }
                int nextX = graph[nextIndex].x;
                int nextY = graph[nextIndex].y;
                if (nextY - nowY < -2) {
                    break;
                }
                if (Math.abs(nextX - nowX) > 2) {
                    continue;
                }
                visited[nextIndex] = visited[nowIndex] + 1;
                q.add(nextIndex);
            }
        }
        return -1;
    }
}