[백준] 7562 나이트의 이동 (JAVA)

풀이

위의 문제는 BFS의 정석이라고도 할수있는 문제이다. 그렇다고 풀었는건 아니다... 문제에서 주어지는 나이트의 최단이동경로에 초점을 두어 최단경로를 구하는 알고리즘을 생각하다 보니 풀지 못하였던 것 같다. 그냥 다음으로 이동할때 이동하기전의 이동횟수에 하나씩 더해가다 어느 순간 goal의 좌표와 현재 좌표가 같게 되면 그때의 이동횟수를 출력하면 문제는 풀린다. 살짝 dp와도 비슷한 점이 있는것 같다. 느낀점은 구현만 확실히 해놓으면 부담없이 전부 탐색하면 될듯하다.

 

package com.company;
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


class point {
    private int x;
    private int y;
    private int cnt;

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

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    public int getCnt() {
        return cnt;
    }
}

class Main {

    static int testCase;
    static int I;
    static point start;
    static point goal;
    static boolean visited[][];
    static int[] dr_x = {-2, -1, 1, 2, 2, 1, -1, -2};
    static int[] dr_y = {1, 2, 2, 1, -1, -2, -2, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), "");

        testCase = Integer.parseInt(st.nextToken());
        for (int t = 0; t < testCase; t++) {
            st = new StringTokenizer(br.readLine(), "");
            I = Integer.parseInt(st.nextToken());
            visited = new boolean[I][I];
            st = new StringTokenizer(br.readLine(), " ");
            start = new point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 0);
            st = new StringTokenizer(br.readLine(), " ");
            goal = new point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 0);

            bw.write(BFS() + "\n");
        }
        bw.flush();
        bw.close();
    }

    public static int BFS(){
        Queue<point> q = new LinkedList<>();
        q.offer(start);
        visited[start.getX()][start.getY()] = true;
        while(!q.isEmpty()){
            point p = q.poll();
            if(p.getX() == goal.getX() && p.getY() == goal.getY())
                return p.getCnt();
            for(int i=0; i<8; i++){
                int temp_x = p.getX() + dr_x[i];
                int temp_y = p.getY() + dr_y[i];

                if(temp_x < 0 || temp_x >=I || temp_y < 0 ||temp_y >= I)
                    continue;

                if(visited[temp_x][temp_y] == false){
                    point temp_point = new point(temp_x, temp_y, p.getCnt()+1);
                    q.offer(temp_point);
                    visited[temp_x][temp_y] = true;
                }
            }
        }
        return -1;
    }
}