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

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

 

 

백준 7562번 문제를 풀기위해서는 BFS 를 활용해야한다. 

 

사실 DFS는 문제를 풀기위한 수식의 일뿐 문제를 이해하고 어떤 방식으로 체크판에 나이트가 움직이는 지를 파악하는게 중요하다.

 

체스판에서 나이트가 움직일 수 있는 경우는 총 8가지 이다. 

 

체크판을 벗어나지 않으면서 이동 할 수 있는 모든 경우를 구하여 그 중 나이트가 이동하고자 하는 판 까지의 이동만 계산하면 된다. 

 

 행 , 열 을 구분하여 이동할 수 있도록 배열에 8가지 경우를 담은 배열을 생성한다. 

static int x[] = {-2, -2, -1, 1, 2, 2, 1, -1};
static int y[] = {-1, 1, 2, 2, 1, -1, -2, -2};

 

이동한 x,y 값을 저장할 수 있는 int배열 Queue 를 생성한다. 

Queue<int[]> que = new LinkedList<>();

//현재 있는 칸 큐에 넣기
que.add(new int[]{fromX,fromY});
visited[fromX][fromY] = true;
result[fromX][fromY] = 0;

 

나이트의 현재 위치를 파악하고 이동할 수 있는 모든 경우를 que에 넣는다. 

int[] c = que.poll();
int nowX = c[0];
int nowY = c[1];

 

체크판의 크기는 한정적이기 때문에 이동할 수 있는 곳도 한정적이다. 8가지의 방법이 있지만 체크판을 벗어나면 해당 위치로 이동하지 못한다. 

범위를 제한하고 , 범위에 적합하면 다음 이동에 +1 을 해서 결과 값에 저장한다. 

 

8가지의 경우를 다 계산한다고 모든 경우를 카운트 하면 안되고 최적의 경로를 구하기 위한 과정임으로 넘어오기 전에 이동에 +1 을 해주면 된다. 

 

//(체크 판 내에서만)다음으로 이동 가능하면 큐에 추가
if(nextX>=0 && nextY>=0 && nextX <l && nextY<l)
{
    if(!visited[nextX][nextY])
    {                          
        que.add(new int[]{nextX,nextY});
        result[nextX][nextY] = result[nowX][nowY] +1;
        visited[nextX][nextY] = true;
    }
}

 

도달하고자 하는 위치에 도달하면 큐를 비운다.

if(nextX == toX && nextY == toY)
{
    //결과 값 을 찾았으니 큐 비우기 
    que.clear();
    break;
}

 

 

*최종코드 

// 7562번 
import java.util.*;
import java.io.*;
public class Main{
    
static Queue<int[]> que = new LinkedList<>();
static int[][] result;
static boolean[][] visited;
static int toX , toY,fromX , fromY ;
static int answer[];
static int l;
static int x[] = {-2, -2, -1, 1, 2, 2, 1, -1};
static int y[] = {-1, 1, 2, 2, 1, -1, -2, -2};

public static void main(String[] args) throws IOException
{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
   //1.테스트 케이스 
   int t = Integer.parseInt(br.readLine());
   //결과값 배열
   answer = new int[t];

   for(int i =0 ;i<t;i++)
   {           
        //체스판의 한변의 길이
        l =  Integer.parseInt(br.readLine()); 

        //체스판 높이 너비 만큼 배열 생성
        visited = new boolean[l][l];
        result = new int[l][l];

        //현재 있는 칸
        st = new StringTokenizer(br.readLine()," ");
        fromX = Integer.parseInt(st.nextToken());
        fromY =  Integer.parseInt(st.nextToken());

        //이동하려는 칸
        st = new StringTokenizer(br.readLine()," ");
        toX = Integer.parseInt(st.nextToken());
        toY =  Integer.parseInt(st.nextToken());  

        bfs();

        answer[i] = result[toX][toY];

   }

   for(int i=0;i<t;i++)
   {
        System.out.println(answer[i]);
   }

}

public static void bfs(){
    Queue<int[]> que = new LinkedList<>();        

    //현재 있는 칸 큐에 넣기
    que.add(new int[]{fromX,fromY});
    visited[fromX][fromY] = true;
    result[fromX][fromY] = 0;

    while(!que.isEmpty())
    {
        int[] c = que.poll();
        int nowX = c[0];
        int nowY = c[1];

        for(int i=0;i<x.length;i++)
        {
            int nextX = nowX +x[i];
            int nextY = nowY +y[i];

            //(체크 판 내에서만)다음으로 이동 가능하면 큐에 추가
            if(nextX>=0 && nextY>=0 && nextX <l && nextY<l)
            {
                if(!visited[nextX][nextY])
                {                          
                    que.add(new int[]{nextX,nextY});
                    result[nextX][nextY] = result[nowX][nowY] +1;
                    visited[nextX][nextY] = true;
                }
            }

            if(nextX == toX && nextY == toY)
            {
                //결과 값 을 찾았으니 큐 비우기 
                que.clear();
                break;
            }
        }            
    }
    }   
}