백준 7562 나이트의 이동

Eunkyung·2021년 11월 12일
0

Algorithm

목록 보기
15/30

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

문제해결

나이트가 이동할 수 있는 범위를 내에서 하나씩 탐색하면서 출발 좌표에서 도착 좌표까지 이동하는데 거치는 최소 칸 수를 구하는 문제이다.
다음 좌표에 이전 좌표값 +1을 해서 구해주면 된다.

소스코드

package graph.b7562;

import javafx.scene.chart.BubbleChart;

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

public class b7562 {
    static int i;
    static int[][] map;
    static boolean[][] check;
    static int[] dx = {-2, -2, -1, 1, 2, 2, 1, -1};
    static int[] dy = {-1, 1, 2, 2, 1, -1, -2, -2};
    static Queue<Point> queue;
    // 출빌 좌표
    static int startX;
    static int startY;
    // 도착 좌표
    static int endX;
    static int endY;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            i = Integer.parseInt(br.readLine());
            map = new int[i][i];
            check = new boolean[i][i];
            StringTokenizer st = new StringTokenizer(br.readLine());
            startX = Integer.parseInt(st.nextToken());
            startY = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            endX = Integer.parseInt(st.nextToken());
            endY = Integer.parseInt(st.nextToken());

            bfs(startX, startY, endX, endY);
            System.out.println(map[endX][endY]);
        }
    }

    public static void bfs(int a, int b, int c, int d) {
        queue = new LinkedList<>();
        queue.add(new Point(a, b));
        check[a][b] = true;

        while (!queue.isEmpty()) {
            Point point = queue.poll();
            // 이동하면서 탐색
            for (int k = 0; k < 8; k++) {
                int nx = point.x + dx[k];
                int ny = point.y + dy[k];
                if (nx >= 0 && ny >= 0 && nx < i && ny < i) {
                    if (!check[nx][ny]) {
                        queue.add(new Point(nx, ny));
                        check[nx][ny] = true;
                        map[nx][ny] = map[point.x][point.y] + 1;
                    }
                }
            }
        }
    }
}

class Point {
    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
profile
꾸준히 하자

0개의 댓글