99클럽 코테 스터디 9일차 TIL BFS(나이트의 이동)

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

 

최소 몇 번만에 이동할 수 있는지 = BFS

이동가능한 방향은 8가지 (-2, 1) (-1, 2) (1, 2) (2, 1) (2, -1) (1, -2) (-1, -2) (-2, -1) 이다.

큐에 들어있는 모든 칸들이 한꺼번에 1번씩 이동하다가 목적지에 도착하는 이동 거리를 계산해야 하므로 qSize 만큼 돌리면서 cnt++ 해주고,

목적지에 도착했을 때의 cnt 값이 답이된다.

 

 

<제출 코드>

package STUDY.Week02;

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 Day09_BOJ_7562_나이트의이동 {

    static class Point{
        int x, y;
        Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    static int l;
    static StringBuilder sb;
    static int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
    static int[] dy = {1, 2, 2, 1, -1, -2, -2, -1};

    public static void bfs(int x, int y, int ex, int ey){
        boolean[][] visited = new boolean[l][l];
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x, y));
        visited[x][y] = true;
        int cnt = 0;
        while(!q.isEmpty()){
            int qSize = q.size();
            // 현재 큐에 들어있는 모든 칸들이 1번 이동
            while(qSize --> 0){
                Point p = q.poll();
                // 이동하려는 칸에 도착
                if(p.x == ex && p.y == ey) sb.append(cnt + "\n");
                // 주어진 8방향으로만 이동 가능
                for(int i=0; i<8; i++){
                    int nx = p.x + dx[i];
                    int ny = p.y + dy[i];
                    if(nx<0 || ny<0 || nx>=l || ny>=l || visited[nx][ny]) continue;
                    q.add(new Point(nx, ny));
                    visited[nx][ny] = true;
                }
            }
            cnt++;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        int t = Integer.parseInt(st.nextToken());
        while(t --> 0){
            st = new StringTokenizer(br.readLine());
            l = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            int ex = Integer.parseInt(st.nextToken());
            int ey = Integer.parseInt(st.nextToken());
            bfs(x, y, ex, ey);
        }
        System.out.println(sb.toString());
    }
}