백준_나이트의 이동(7562) in Java

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

7562번: 나이트의 이동

풀이

- 일반적인 BFS 문제에서 나이트가 이동할 수 있는 범위가 다르기때문에 그에 맞춰 배열을 만들어준다

- 이동할때 배열에 +1 씩 해줘 이동횟수를 기록한다.

- 목표지점에 도착하면 그 배열의 값을 출력한다.

- 출발점과 시작 점이 같으면 0을 출력하게한다. 

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 int[] dx = {2, 1, 2, 1, -2, -1, -2, -1};
    static int[] dy = {1, 2, -1, -2, 1, 2, -1, -2};
    static int[][] cnt;
    static boolean[][] visited;
    static int a;
    static XY start, finish;
    static Queue<XY> que = new LinkedList<>();

    static class XY{
        int x;
        int y;

        public XY(int x,int y) {
            this.x = x;
            this.y=y;
        }
    }
    static int bfs(){
        que = new LinkedList<>();
        que.offer(start);
        visited[start.x][start.y] = true;
        while (!que.isEmpty()){
            XY tmp = que.poll();
            if(tmp.x== finish.x&&tmp.y== finish.y) {
                return cnt[tmp.x][tmp.y];
            }
            for (int i = 0; i < 8; i++) {
                int cx = tmp.x + dx[i];
                int cy = tmp.y + dy[i];
                if(0<=cx&&cx<a&&0<=cy&&cy<a){
                    if(!visited[cx][cy]){
                        visited[cx][cy]=true;
                        cnt[cx][cy]=cnt[tmp.x][tmp.y]+1;
                        que.offer(new XY(cx, cy));
                    }
                }
            }
        }
        return 0;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int i=0;i<T;i++){
            a = Integer.parseInt(br.readLine());
            cnt= new int[a][a];
            visited = new boolean[a][a];
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            start = new XY(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            st = new StringTokenizer(br.readLine(), " ");
            finish = new XY(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

           if(start.x== finish.x&&start.y== finish.y){
               System.out.println(0);
           }else{
               System.out.println(bfs());
           }

        }
    }
}

- 테스트 횟수가 1이상일수도 있기 때문에 bfs()를 시작할때는 초기화 해줘야 된다는 것을 생각하지못해서 마지막에 어려웠다.