[백준]JAVA - 2412번: 암벽 등반

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

2412번: 암벽 등반

🔶 풀이

BFS로 충분히 해결할 수 있는 문제.

 

(0, 0)에서 시작해서 (x, T)까지 올라가면 된다.

우선 입력값을 y값을 기준으로 배열을 만들어서 입력해줬다.

rock = new ArrayList[200001]; // T의 최대값: 2,000,000
for (int i=0; i<200001; i++) {
    rock[i] = new ArrayList<>();
}

배열의 크기는 T의 최대값인 2,000,000에서 +1을 해준 값 2000001로 설정해줬다.

 

현재 위치(0, 0)를 queue에 입력해주고 BFS 탐색을 진행하면 된다.

현재 위치에서 ±2 까지 한 번에 이동할 수 있다고 했으니까 Queue에서 하나의 값을 꺼내면 현재 위치에서 x, y좌표 ±2의 범위를 모두 탐색해준 후에 이동 횟수(ans)를 늘려줘야한다.

 

ans: 현재 이동 횟수

q: 현재 위치

rock: 암벽에 박힌 홈

 

<최종코드>

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

public class Main {
    static int N, T;
    static ArrayList<Integer>[] rock;
	
    public static class Pos {
        int x, y;
		
        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
	
    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()); // 정상 위치 (y)
		
        rock = new ArrayList[200001]; // T의 최대값: 2,000,000
        for (int i=0; i<200001; i++) {
            rock[i] = new ArrayList<>();
        }
		
        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);
        }
        
        // ★ 높이에 따른 x값 오름차순 정렬
        for (int i=0; i<200001; i++) {
            Collections.sort(rock[i]);
        }
		
        System.out.println(bfs());
    }
	
    public static int bfs() {
        Queue<Pos> q = new LinkedList<>();
        q.add(new Pos(0, 0));
		
        int ans = 0;
        while (!q.isEmpty()) {
            int size = q.size();
			
            for (int i=0; i<size; i++) {
                Pos now = q.poll();
				
                if (now.y == T) {
                    return ans; 
                }
				
                for (int y=now.y-2; y<=now.y+2; y++) {
                    if (y < 0 || y >= 200001) continue;
					
                    for (int x=0; x<rock[y].size(); x++) {
                        if (now.x + 2 < rock[y].get(x)) break; // 큰 값이 나오면 볼 필요 없음
                        else if (now.x - 2 > rock[y].get(x)) continue; 
							
                        q.add(new Pos(rock[y].get(x), y));
                        rock[y].remove(x); // 암벽 제거
                        x--;               // remove를 하면 인덱스값이 작아지기때문에 -1
                    }
                }
            }
            ans++;
        }
		
        return -1;
    }
}