[백준] 7562번: 나이트의 이동

📝문제

평소에 풀던 것보다 쉬운 난이도의 문제라 그런지 쉽게 풀 수 있었다.
보자마자 BFS 문제다 싶었고, 머리 속에 떠올렸던 로직을 바로 구현하여 해결했다.

📌코드

package Baekjoon;

import java.util.*;
import java.io.*;
public class BOJ7562 {

    static int t;
    //나이트가 이동할 수 있는 방향
    static int[] moveY = {-1, -2, -2, -1, 1, 2, 2, 1};
    static int[] moveX = {-2, -1, 1, 2, 2, 1, -1, -2};

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

        t = Integer.parseInt(st.nextToken());

        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken());
            int[][] visited = new int[l][l]; //각 칸에 최소 몇 번으로 도달했는지 기록한다
            st= new StringTokenizer(br.readLine());
            int startY = Integer.parseInt(st.nextToken());
            int startX = Integer.parseInt(st.nextToken());
            st= new StringTokenizer(br.readLine());
            int endY = Integer.parseInt(st.nextToken());
            int endX = Integer.parseInt(st.nextToken());

            Queue<int[]> q= new LinkedList<>();
            q.add(new int[] {startY, startX});

            while(!q.isEmpty()){
                int[] curPnt = q.poll();
                int curY = curPnt[0];
                int curX = curPnt[1];
                if(curX == endX && curY == endY) {
                    System.out.println(visited[curY][curX]);
                    break;
                }
                for(int j = 0; j < 8; j++){
                    int nextY = curY + moveY[j];
                    int nextX = curX + moveX[j];
                    //이전 칸의 수에서 1씩 더해준다
                    //범위 검사
                    if(nextX < 0 || nextX >= l || nextY < 0 || nextY >= l) continue;
                    if(visited[nextY][nextX] != 0) continue;
                    q.add(new int[] {nextY, nextX});
                    visited[nextY][nextX] = visited[curY][curX] + 1;
                }
            }
        }
    }
}

좋은 웹페이지 즐겨찾기