백준-7562번/나이트의 이동(java)

 

 

문제 이해

 

그래프 문제들은 기본적인 틀을 벗어나지 않는 것 같다.

DFS, BFS만 구현을 잘 한다면 그래프 문제를 보다 쉽게 풀 수 있을 것 같다는 생각이 든다.

 

 

 

이 문제는 전에 풀었던 2178번 미로 탐색 문제와 매우 유사한 느낌이다.

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

 

다만 차이점이라고 하면 이번 문제는 이동 방법을 더 고민 해봐야 한다는 점이다.

 

이동 방법

1) X축으로 2 or -2만큼 이동한 경우 ==> Y축으로 -1 or 1만큼 이동

 

2) X축으로 -1 or 1만큼 이동한 경우 ==> Y축으로 -2 or 2만큼 이동

 

이러한 규칙을 수행하기 위해 이번에는 dx dy 배열이 더욱 길어졌다

static int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
static int[] dy = {1, 2, 2, 1, -1, -2, -2, -1};

 

 

문제 풀이

 

<BFS 함수>

public static void BFS(int nowX, int nowY){
    Queue<int[]> queue = new LinkedList<>();
    queue.add(new int[]{nowX,nowY});
    visit[nowX][nowY]=true;

    while(!queue.isEmpty()){
        int[] point=queue.poll();
        int pointX=point[0];
        int pointY=point[1];

        for(int i=0; i<8; i++){
            int nextX=pointX+dx[i];
            int nextY=pointY+dy[i];

            if(nextX<0 || nextY<0 || nextX>=N || nextY>=N){
                continue;
            }
            if(visit[nextX][nextY]){
                continue;
            }

            queue.add(new int[]{nextX,nextY});
            arr[nextX][nextY]=arr[pointX][pointY]+1;
            visit[nextX][nextY]=true;

        }

    }




    }

 

역시나 BFS를 구현하기 위해서는 큐가 필요하다.(이번 문제 에서는 배열을 이용해 그래프를 구현하므로 배열을 담을 수 있는 큐가 필요)

 

dx, dy 배열을 순회하면서 이동 가능한 경우 8가지를 모두 순회 한다.

 

그래프의 범위를 벗어난다면 이동하지 않는다.

 

<전체 코드>

import java.util.*;

public class Problem7562 {

    static int[][] arr;
    static int N;
    static boolean[][] visit;
    static int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
    static int[] dy = {1, 2, 2, 1, -1, -2, -2, -1};

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int Case = scanner.nextInt();

        for(int i=0; i<Case; i++){
            N=scanner.nextInt();
            int nowX=scanner.nextInt();
            int nowY=scanner.nextInt();
            int x=scanner.nextInt();
            int y=scanner.nextInt();
            visit=new boolean[N][N];
            arr=new int[N][N];
            BFS(nowX,nowY);
            System.out.println(arr[x][y]);
        }
    }

    public static void BFS(int nowX, int nowY){
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{nowX,nowY});
        visit[nowX][nowY]=true;

        while(!queue.isEmpty()){
            int[] point=queue.poll();
            int pointX=point[0];
            int pointY=point[1];

            for(int i=0; i<8; i++){
                int nextX=pointX+dx[i];
                int nextY=pointY+dy[i];

                if(nextX<0 || nextY<0 || nextX>=N || nextY>=N){
                    continue;
                }
                if(visit[nextX][nextY]){
                    continue;
                }

                queue.add(new int[]{nextX,nextY});
                arr[nextX][nextY]=arr[pointX][pointY]+1;
                visit[nextX][nextY]=true;

            }

        }




        }

    }