문제링크

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

구현방법

나이트를 이동시켜서 정해진 위치에 도달하는 데 걸리는 총 이동거리를 구하는 것으로 근처를 먼저 탐색하면서 진행해야합니다. 그렇기 때문에 이동하는 곳을 탐색하면서 진행하며 최소 이동거리를 구하기 때문에 이전에 왔던 곳을 다시 오게 되면 중복이 발생해서 최소 이동거리가 될 수없습니다. 그래서 boolean을 통해서 위치를 체크하면서 진행합니다. 도착하게되면 탐색을 바로 종료시키며 값을 리턴합니다.

구현알고리즘

너비 우선 탐색(BFS)

CODE

package com.backjoon.Silver.p7562;

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

public class Main {

    static class Point{
        int row;
        int col;
        int moving;

        public Point(int row,int col, int moving){
            this.row = row;
            this.col = col;
            this.moving = moving;
        }
        public Point(int row,int col){
            this.row = row;
            this.col = col;
        }
    }
    private static int T;

    //이동 방법 8가지
    static int dx[] ={-1,-2,-2,-1,1,2,2,1};
    static int dy[] ={-2,-1,1,2,2,1,-1,-2};

    static int Map_size;
    static boolean check[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        T = Integer.parseInt(br.readLine());

        StringBuilder sb= new StringBuilder();
        StringTokenizer st;

        for(int test = 0; test < T; test++){
            int move = -1;
            Map_size = Integer.parseInt(br.readLine());
            check = new boolean[Map_size][Map_size];
            st = new StringTokenizer(br.readLine());
            //시작점
            Point start = new Point(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),0);
            st= new StringTokenizer(br.readLine());
            //도착점
            Point end = new Point(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));

            if(start.row == end.row && start.col == end.col){
                sb.append(0).append("\n");
                continue;
            }else{
                move = BFS(start,end);
                sb.append(move).append("\n");
            }

        }
        System.out.println(sb);
    }

    //BFS 탐색으로 나이트를 이동시키면서 이동 횟수 누적
    public static int BFS(Point start,Point end){
        Queue<Point> queue = new LinkedList<>();
        queue.offer(start);
        check[start.row][start.col] = true;
        while(!queue.isEmpty()){
            Point cur = queue.poll();
            //
            if(cur.row == end.row && cur.col == end.col){
                return cur.moving;
            }
            for(int idx = 0; idx <8;idx++){
                int nxt_x = cur.row + dx[idx];
                int nxt_y = cur.col + dy[idx];

                //맵을 벗어나는경우는 제외
                if(nxt_x < 0 || nxt_x >= Map_size || nxt_y <0 ||nxt_y >= Map_size || check[nxt_x][nxt_y]){
                    continue;
                }
                queue.offer(new Point(nxt_x,nxt_y, cur.moving+1));
                check[nxt_x][nxt_y] = true;
            }
        }

        return 0;
    }
}