백준 7562_나이트의 이동_JAVA

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

7562번: 나이트의 이동

import java.util.*;
import java.io.*;


public class Main {
    static int T, N;
    static int[][] grid;
    static boolean[][] visited;
    static int fx, fy;
    static int count;
    static int[] dx = {-2, -2, -1, 1, 2, 2, 1, -1};
    static int[] dy = {-1, 1, 2, 2, 1, -1, -2, -2};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine()); // 테스트 케이스 갯수
        for (int i = 0; i < T; i++) {
            N = Integer.parseInt(br.readLine()); // 체스판 한 변의 길이
            grid = new int[N][N];
            visited = new boolean[N][N];
            count = 0;

            StringTokenizer st = new StringTokenizer(br.readLine());
            int cx = Integer.parseInt(st.nextToken()); // 현재 위치
            int cy = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            fx = Integer.parseInt(st.nextToken()); // 도착 위치
            fy = Integer.parseInt(st.nextToken());

            bfs(cx, cy, 0);

            System.out.println(count);
        }

    }

    private static void bfs(int x, int y, int c) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y, c});
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            int[] now = queue.poll();
            if (now[0] == fx && now[1] == fy) {
                count = now[2];
                break;
            }
            for (int i = 0; i < 8; i++) {
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                int nc = now[2] + 1;

                if (nx >= 0 && ny >= 0 && nx < N && ny < N && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    queue.add(new int[]{nx, ny, nc});
                }
            }
        }
    }
}

 

 

회고

- 기본적인 BFS문제였다.

- 금방 풀려서 기분이 좋다.