백준 7562 나이트의 이동 자바 알고리즘 java 풀이

 

백준 7562 나이트의 이동 알고리즘

해당 문제는 최단거리를 묻는 문제다. 출발 지점의 좌표에서 시작해서 도착 지점까지의 최단거리를 구하기 위해서는 DFS보다는 BFS 알고리즘을 사용해서 문제의 해법을 찾아야 한다. 즉 1칸씩 이동할 때 마다 counter를 증가시키면서 도착지점까지의 최단거리를 구하는 문제다.

 

BFS 알고리즘에서는 Queue 자료구조를 사용한다. while문을 돌면서 queue 내의 더 이상의 데이터가 없을 때 까지 무한 반복이 진행되며, 만약 새로운 지점을 찾게 되면 queue에 지점의 좌표값을 입력하면서 BFS 알고리즘 탐색을 이어 나간다. 혹시나 BFS, DFS 알고리즘이 처음이라면 아래 글들을 다 읽고 문제를 푸는 것을 추천한다.

 

BFS, DFS 알고리즘

 

백준 1697 숨바꼭질 문제 자바 JAVA BFS 알고리즘 풀이

 

백준 7569 토마토 3D 알고리즘 문제 자바 JAVA 풀이 해설 리뷰

 

백준 7576 토마토 알고리즘 문제 자바 JAVA CODE

 

백준 7562번에서 조금 다른 점은 체스의 나이트의 이동 방법으로 최단 거리를 구한다는 점이다. 기존 최단거리 문제에서는 이동방법이 상,하,좌,우 4가지 방법이었지만 나이트의 이동은  총 8가지 방법이 존재한다.

 

 

체스판에서 나이트의 이동의 방법이 8가지 이므로 출발지점에서 나이트의 이동방식으로 도달할 수 있는 곳의 좌표를 지정해주고, 해당 좌표에 도착할 때 마다 counter를 증가시키는 방법으로 최단거리를 구해야 한다.

 

예를 들어 8칸 짜리 체스판에서 나이트의 이동으로 최단거리를 계산하면 counter 2차 배열의 모습은 다음과 같다. (0,0)에서 출발해서 (7,7)까지 도달하는  방문 순서의 결과값이다. 한번 방문한 지점은 boolean 값으로 처리해주면서 다음 지점을 찾아나간다.

0 3 2 3 2 3 4 5
3 4 1 2 3 4 3 4
2 1 4 3 2 3 4 5
3 2 3 2 3 4 3 4 
2 3 2 3 4 3 4 5
3 4 3 4 3 4 5 4
4 3 4 3 4 5 4 5
5 4 5 4 5 4 5 6

 

 

 

 

 

 

백준 7562 나이트의 이동 자바

/*
    Owner : Developer Blog
    Title : 체스 나이트 문제
    Algorithm : BFS 알고리즘
    Date : 2022-03-22
*/

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class A_7562 {

    static class Points{
        int x;
        int y;

        public Points(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    private static int X,N;
    private static int[] startPoint;
    private static int[] endPoint;
    private static Queue<Points> queue;

    private static int[][] counter;
    private static boolean[][] visit;

	// 나이트의 8가지 이동 방법
    private static int[] NEW_X = {-2, -1, 1, 2, 2, 1, -1, -2};
    private static int[] NEW_Y = {-1, -2, -2, -1, 1, 2, 2, 1};

    private static StringBuilder sb = new StringBuilder();

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);

        X = in.nextInt();
                
        for(int i=0; i<X; i++){

            counter = new int[301][301];
            visit = new boolean[301][301];
            startPoint= new int[2];
            endPoint = new int[2];
            queue =  new LinkedList<>();

            // 정사각형의 크기
            N = in.nextInt();

            // 시작 포인트 입력
            for(int j=0; j<2; j++){
                startPoint[j] = in.nextInt();
            }

            // 목적 포인트 입력
            for(int k=0; k<2; k++){
                endPoint[k] = in.nextInt();
            }

            sb.append(bfs(startPoint[0], startPoint[1])+"\n");
            
        }
        System.out.println(sb);

    }

    private static int bfs(int x, int y){
        queue.add(new Points(x,y));
        visit[y][x] = true;

        while(!queue.isEmpty()){
            Points temp = queue.poll();

            if(temp.x==endPoint[0] && temp.y==endPoint[1]){
                return counter[endPoint[1]][endPoint[0]];
            }

            for(int i=0; i<8; i++){
                int new_X = temp.x + NEW_X[i];
                int new_Y = temp.y + NEW_Y[i];
                if(new_X>=0 && new_Y>=0 && new_X<N && new_Y<N){
                    if(!visit[new_Y][new_X]){
                        queue.add(new Points(new_X, new_Y));
                        visit[new_Y][new_X]=true;
                        counter[new_Y][new_X] = counter[temp.y][temp.x]+1;
                    }
                }
                
            }
        }

        return -1;

    }
}

 

 

백준 7562 나이트의 이동 자바 결과