[BAEKJOON] 7562번 : 나이트의 이동 (JAVA)

- 알고리즘 분류 : BFS

- 사용 언어 : JAVA

 

 

소스 설명은 주석을 참고해주세요.

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 Pos {
        int y;
        int x;
        int cnt;

        public Pos(int y, int x) {
            this.y = y;
            this.x = x;
            this.cnt = 0;
        }

        public Pos(int y, int x, int cnt) {
            this.y = y;
            this.x = x;
            this.cnt = cnt;
        }
    }

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

        int[] ymove = {2, 2, -2, -2, -1, 1, -1, 1};
        int[] xmove = {1, -1, 1, -1, -2, -2, 2, 2};

        int N = Integer.parseInt(br.readLine());
        for(int i=0; i<N; i++) {
            int L = Integer.parseInt(br.readLine());
            boolean[][] visited = new boolean[L][L];

            StringTokenizer st = new StringTokenizer(br.readLine());
            Pos start = new Pos(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

            st = new StringTokenizer(br.readLine());
            Pos end = new Pos(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

            Queue<Pos> q = new LinkedList<>();
            visited[start.y][start.x] = true;
            q.offer(start);

            while(!q.isEmpty()) {
                Pos now = q.poll();
                if(now.y == end.y && now.x == end.x) {
                    sb.append(now.cnt + "\n");
                    break;
                }

                for(int j=0; j<8; j++) {
                    int tempY = now.y + ymove[j];
                    int tempX = now.x + xmove[j];

                    if(tempY < 0 || tempY >= L || tempX < 0 || tempX >= L) continue;
                    if(visited[tempY][tempX])   continue;

                    visited[tempY][tempX] = true;
                    q.offer(new Pos(tempY, tempX, now.cnt+1));
                }
            }
        }

        System.out.println(sb.toString());
    }
}