BOJ) 나이트의 이동

나이트의 이동

7562번: 나이트의 이동

풀이

 

테스트 케이스의 수가 주어지고, 각 테스트 케이스마다 체스판의 크기, 시작점, 목표 지점이 차례대로 주어진다.

나이트가 시작점을 출발해서 목표 지점에 도달하는 경우의 수를 출력하는 문제다.

 

나이트 이동 가능 칸

나이트가 이동할 수 있는 경우의 수는 8가지다.위의 8가지 경우의 x와 y가 움직이는 위치를 각각 dx와 dy로 선언해줬다.그리고 BFS를 통해서 이미 도착했던 지점인지 visit체크와 함께 움직일 때마다 step을 저장해주면서, 도착지점에 도달하면 step을 반환하여 답을 출력할 StringBuffer에 저장했다.

가장 기본적인 BFS 문제였다.

 

 

 

코드

 

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    static int[] dx ={-1,-2,-2,-1,1,2,2,1}, dy={-2,-1,1,2,2,1,-1,-2};

    public static void main(String[] args) throws IOException {
        solution(new BufferedReader(new InputStreamReader(System.in)));
    }

    private static void solution(BufferedReader br) throws IOException {
        int testCase = Integer.parseInt(br.readLine());
        StringBuffer sb = new StringBuffer();
        final String NEWLINE = "\n";

        for(int i=0; i<testCase; i++) {
            int n = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            Pos start = new Pos(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()),0);
            st = new StringTokenizer(br.readLine());
            Pos dest = new Pos(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()),0);

            sb.append(getMove(start,dest,n)).append(NEWLINE);
        }
        System.out.println(sb.toString());
        br.close();
    }

    private static int getMove(Pos start, Pos dest, int n) {
        int result =0;
        LinkedList<Pos> moveList = new LinkedList<>();
        moveList.offer(start);
        boolean[][] visit = new boolean[n][n];
        visit[start.y][start.x] = true;

        while(!moveList.isEmpty()) {
            Pos pos = moveList.poll();
            if(pos.x == dest.x && pos.y == dest.y) {
                result = pos.step;
                break;
            }
            for(int i=0; i<8; i++) {
                int nx = pos.x+dx[i];
                int ny = pos.y+dy[i];
                int step = pos.step+1;
                if(inInArea(nx,ny,n)) {
                    if(!visit[ny][nx]) {
                        visit[ny][nx] = true;
                        moveList.offer(new Pos(nx,ny,step));
                    }
                }
            }
        }
        return result;
    }

    private static boolean inInArea(int x, int y, int n) {
        return x>=0 && x<n && y>=0 && y<n;
    }

    private static class Pos {
        int x,y,step;
        public Pos(int x, int y, int step) {
            this.x = x;
            this.y = y;
            this.step = step;
        }
    }
}