백준 - 그래프와 순회 나이트의 이동 7652문제 / BFS풀이, 오답

 

 

첫째 줄에는 체스판의 한 변의 길이

둘째 줄에는 나이트가 현재 있는 칸

셋재 줄에는 나이트가 이동하려는 칸이 주어진다.

0, 0에서 시작해서 -> 7, 0 도착

최소 몇 번만에 이동할 수 있는지 확인하는 문제다.

=> BFS를 이용해서 최솟값을 구하자

 

처음 나이트가 이동할 수 있는 경우의 수, 

가운데 시작에서 나이트는 저렇게 이동할 수 있음을 알고 시작하자.

 

col, row / col2, row2를 따로 나누었다.

 

 

2차원 배열을 생성해서 예를 들어보자.

이런식으로 이동할 수 있음을 나타낸다.

 

두 번째, col2와 row2를 이용했을 때 이동할 수 있는 예를 들어보자.

이렇게 이동함을 알 수 있다.

 

그럼 이제 같이 이동했을 때를 나타내보자

겹칠 일이 없이, 내가 이동할 수 있는 좌표를 Queue에 담고 한 번에 처리하는 과정이다.

 

 

최종 2차원 배열

따라서 마지막 좌표의 값에서 -1을 빼준 값이 정답이다! 그 이유는 0, 0에서 1로 시작했기 때문에 하나 빼주는 거임!

 

 

 
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 {
    public static int t; // 테스트 케이스 갯수
    public static int l; // 체스판의 한 변의 길이
    public static int n, m; // 두 수의 쌍 (시작점)
    public static int a, b; // 두 수의 쌍 (도착점)
 
 
    public static int[][] arr;
    public static boolean[][] visit;
 
    public static int[] col = {1, -1, 1, -1};
    public static int[] row = {2, 2, -2, -2};
 
    public static int[] col2 = {2, -2, 2, -2};
    public static int[] row2 = {1, 1, -1, -1};
 
    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());
            l = Integer.parseInt(st.nextToken()); // 체스판 크기
 
            arr = new int[l][l]; // 체스판의 크기를 2차원 배열로 생성
            visit = new boolean[l][l];
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
 
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
 
            bfs();
            System.out.println(arr[a][b] - 1);
        }
 
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }
 
    public static void bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{n, m});
        arr[n][m] = 1;
        visit[n][m] = true;
 
        while (!q.isEmpty()) {
            int[] nowLocation = q.poll();
            int y = nowLocation[0];
            int x = nowLocation[1];
 
 
 
            for (int i = 0; i < 4; i++) {
                System.out.println("현재Y값 = " + nowLocation[0]);
                System.out.println("현재X값 = " + nowLocation[1]);
                int newY = nowLocation[0] + row[i];
                int newX = nowLocation[1] + col[i];
 
                if (newY < 0 || newX < 0 || newY >= l || newX >= l) {
                    continue;
                }
 
                if (visit[newY][newX] || arr[newY][newX] != 0) {
                    continue;
                }
 
                q.offer(new int[]{newY, newX});
                arr[newY][newX] = arr[y][x] + 1;
                System.out.println("newY위 아래 2칸 = " + newY);
                System.out.println("newX위 아래 2칸 = " + newX);
                visit[newY][newX] = true;
            }
 
 
            for (int i = 0; i < 4; i++) {
                System.out.println("현재Y값 = " + nowLocation[0]);
                System.out.println("현재X값 = " + nowLocation[1]);
                int newY = nowLocation[0] + row2[i];
                int newX = nowLocation[1] + col2[i];
 
                if (newY < 0 || newX < 0 || newY >= l || newX >= l) {
                    continue;
                }
 
                if (visit[newY][newX] || arr[newY][newX] != 0) {
                    continue;
                }
 
                q.offer(new int[]{newY, newX});
                arr[newY][newX] = arr[y][x] + 1;
                System.out.println("newY 왼 오 2칸 = " + newY);
                System.out.println("newX 왼 오 2칸 = " + newX);
                visit[newY][newX] = true;
            }
            System.out.println("\"ok\" = " + "ok");
        }
 
    }
}