[문제 풀이] 백준 7562번 나이트의 이동 JAVA

문제

 

  문제접근 방법   

해당 문제에서는 여러 테스트 케이스들이 주어지는데 각각의 테스트 케이스들은 체스판의 크기 l(체스판은 l x l 크기), 시작 좌표와 이동하려는 좌표 값이다. 해당 값들을 가지고 l x l 크기 체스판에서 나이트가 시작점에서 이동하려는 점까지 최소 몇 번 만에 이동하는지를 구하는 프로그램을 작성하는 것이 본 문제의 요구사항이다.

본문제는 최단거리 구하는 문제와 같은 문제라고 생각된다. 문제에서는 최단이 아닌 최소 몇번만에 이동 가능한지라고 물었지만 본인은 최단거리와 문제와 같이 bfs로 문제를 접근하여 풀이하기로 하였다.

여기서 핵심은 최소 거리를 어떤식으로 카운트하는지와 단순 상하좌우 이동이 아닌 나이트가 이동할 수 있는 경우의 수를 잘 설정하는지이다. 최종 코드는 다음과 같다.

 

< 최종 코드 >

import java.util.*;

public class Main{
    public static boolean visited[][];
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        
        int test=sc.nextInt();
        for(int t=0;t<test;t++){
            int l=sc.nextInt();
            visited=new boolean[l][l];
            int coordX[]=new int[2];
            int coordY[]=new int[2];
            for(int i=0;i<2;i++){
                coordX[i]=sc.nextInt();
                coordY[i]=sc.nextInt();
            }
            bfs(coordX,coordY);
        }
    }
    public static void bfs(int x[],int y[]){
        Queue<int []> q=new LinkedList<>();
        visited[x[0]][y[0]]=true;
        q.add(new int[]{x[0],y[0],0});
        int dx[]={-2,-2,-1,1,2,2,-1,1};
        int dy[]={-1,1,2,2,1,-1,-2,-2};
        while(!q.isEmpty()){
            int xy[]=q.poll();
            if(xy[0]==x[1]&&xy[1]==y[1]){
                System.out.println(xy[2]);
                return;
            }
            for(int i=0;i<8;i++){
                int nx=dx[i]+xy[0];
                int ny=dy[i]+xy[1];
                if(nx>=0&&ny>=0&&nx<visited.length&&ny<visited.length){
                    if(!visited[nx][ny]){
                        visited[nx][ny]=true;
                        q.add(new int[]{nx,ny,xy[2]+1});
                    }
                }
            }
        }
    }
}

처음에는 이동할때마다 카운트하는 부분을 전역변수로 두어야하나라고 생각했지만 그럴경우 갱신에 어려움이 존재한다고 판단하여

위의 코드처럼 q에 x,y값을 넘길때 같이 넘겨 관리하는 방식으로 구현하였다. 이렇게 구현할 경우 이동할때 현재 위치까지 몇번 이동했는지를 같이 갱신가능해 위에서 언급했던 핵심중한 부분을 어렵지 않게 해결이 가능했다.

마지막으로 나이트의 이동가능한 경우를 설정해야하는데 일반적으로 상하좌우를 x[]={-1,1,0,0} y[]={0,0,-1,1} 이런식으로 표현하지만 나이트는 상하좌우가 아닌 각각 상하좌우로 2칸이동후 좌우상하로 한칸씩이동하는 방식인것을 확인할 수 있었다.

그래서 위에서 설정한것처럼 x=-2이면 y=1 ,y=-1 과 같이 설정하여 문제를 해결하였다.

 

 

  마무리  

해당 문제는 위에서 언급하였던 핵심인 나이트의 이동경우 설정과 카운트 관리만 잘해준다면 어려움 없이 문제를 해결할 수 있을 것이라고 생각된다.