[백준알고리즘] bfs - 7562번 나이트의 이동 문제

 

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

7562번: 나이트의 이동

bfs 활용문제

x가 행을 나타내고 y가 열을 나타내는 의미로 했는데

이 두개 순서를 헷갈려서 여기저기 잘못써놓느라 몇번만에 맞았다..

아오~헷갈리니까 다음부터는 x, y 말고 col, row로 쓰던지 해야겠다.

아직도 행, 열이 헷갈리다니..........

 

package baekjoonWeek5;

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ_7562 {  //백준 나이트의 이동 문제
    static Queue<Point> q = new LinkedList<>();
    static int[][] check;
    static int[] dx = {-1, 1, 2, 2, 1, -1, -2, -2 };
    static int[] dy = {-2, -2, -1, 1, 2, 2, -1, 1};
    static int l;

    static class Point{
        int x; int y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

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

        for (int i = 1; i <= T; i++) {
            l = Integer.parseInt(br.readLine());
            check = new int[l][l];
            int curX; int curY;     //현재위치의 각 열, 행
            StringTokenizer st = new StringTokenizer(br.readLine());
            curY = Integer.parseInt(st.nextToken());
            curX = Integer.parseInt(st.nextToken());

            int toGoX; int toGoY;   //가려는 위치의 각 열, 행
            st = new StringTokenizer(br.readLine());
            toGoY = Integer.parseInt(st.nextToken());
            toGoX = Integer.parseInt(st.nextToken());

            q.add(new Point(curX, curY));   //시작점 큐에 추가
            bfs(toGoX, toGoY);
            bw.write(Integer.toString(check[toGoY][toGoX]));
            bw.newLine();
            q.clear();

        }
        bw.flush();
        bw.close();
    }

    static void bfs(int x, int y) {
        while (!q.isEmpty()) {
            Point point = q.poll();
            if (point.x == x && point.y == y) {
                return;
            }
            for (int i = 0; i < 8; i++) {
                int tmpx = point.x + dx[i];
                int tmpy = point.y + dy[i];
                if(tmpy >= 0 && tmpy < l && tmpx >= 0 && tmpx < l && check[tmpy][tmpx] == 0){   //아직 방문안했고 갈수있는 배열범위 내라면
                    q.add(new Point(tmpx, tmpy));
                    check[tmpy][tmpx] = check[point.y][point.x] + 1;
                }
            }
        }

    }
}