[BOJ] 2412 - 암벽 등반

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

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

2412번: 암벽 등반

난이도: 골드 3

사용언어: JAVA

 

풀이

 

기본적인 BFS를 사용하면 쉽게 해결할 수 있는 문제입니다.

 

단, 다음의 문장만 유의해서 풀이를 하시면 됩니다.

 

각각의 홈의 좌표는 (x, y)와 같이 표현되는데, |a - x| ≤ 2이고 |b - y| ≤ 2이면 (x, y)에서 (a, b)로 이동할 수 있다. 

 

BFS를 수행하면서 이동할 홈의 x, y 값을 항상 검사하면서 진행하면 됩니다.

 

import java.util.*;
import java.io.*;
 
public class Main {
 
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, T;
 
    static class node{
        int x; // x좌표
        int y; // y좌표
        boolean visit; // 해당 홈에 대한 방문 여부
 
        node(int x, int y, boolean v){
            this.x = x;
            this.y = y;
            this.visit = v;
        }
    }
 
    static ArrayList<ArrayList<node>> list = new ArrayList<>(); // 홈의 위치를 저장할 2차원 ArrayList
    static Queue<node> q = new LinkedList<>(); //BFS용 Queue
 
    public static void main(String[] args) throws IOException {
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());
 
        for (int i = 0; i <= T; i++) {
            list.add(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());
 
            list.get(y).add(new node(x, y, false)); // ArrayList에 홈의 좌표 정보 기입
        }
 
        q.add(new node(0,0,false)); // 최초 0,0에서 출발
        int cnt = 0;
        while(!q.isEmpty()){
            int qsize = q.size();
 
            for (int i = 0; i < qsize; i++) {
                node now = q.poll();
                if(now.y == T){ // 암벽의 꼭대기에 도착
                    bw.write(String.valueOf(cnt));
                    bw.flush();
                    bw.close();
                    br.close();
                    System.exit(0); // 종료
                }
 
                for (int j = now.y - 2; j <= now.y + 2; j++) { // |b - y| ≤ 2이면 (x, y)에서 (a, b)로 이동할 수 있다. 
                    if(j < 0 || j > T){
                        continue;
                    }
 
                    for (int k = 0; k < list.get(j).size(); k++) {
                        node next = list.get(j).get(k);
 
                        if(Math.abs(now.x - next.x) <= 2 && next.visit == false){ // |a - x| ≤ 2이면 (x, y)에서 (a, b)로 이동할 수 있다, 방문 체크
                            next.visit = true; // 방문 여부 업데이트
                            q.add(next); 
                        }
                    }
                }
            }
 
            cnt++;
        }
 
        bw.write("-1");
        bw.flush();
        bw.close();
        br.close();
    }
}