[백준 BFS] 7562번: 나이트의 이동 (Java)

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

 

기본적인 BFS 유형의 틀을 지키고 있는 문항이다.

먼저 필요한 데이터들을 선언한다 : dx, dy, visited, board, static Class Pair, Queue

이후 첫 시작점에 대한 Pair 객체를 생성, 큐에 넣고 방문 처리(visited = true)한다.

while문을 돌리고, 그 속에서 큐의 Pair 객체를 꺼내고 이동 가능한 거리들을 확인(검증), 이동 가능한 위치에 대해 Pair 객체를 생성, 큐에 다시 넣는다.

큐의 Pair 객체를 꺼내었을 때 x값과 y값이 목적지 x값 y값과 동일할 때까지 while문을 반복한다.

 

나이트가 이동 가능한 거리로는 아래와 같다.

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

해당 dx dy에 대해 검증을 수행하고 검증에 통과한 Pair들만 큐에 넣는다.

 

 

package main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;



public class Main {

    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int TC = Integer.parseInt(br.readLine());
        int[] dx = {-2, -2, 2, 2, 1, 1, -1, -1};
        int[] dy = {1, -1, 1, -1, 2, -2, 2, -2};
        List<Integer> outputList = new ArrayList<>();

        for(int i=0; i<TC; i++) {
            int l = Integer.parseInt(br.readLine());

            int[][] arr = new int[l][l];
            boolean[][] visited = new boolean[l][l];

            String[] input1 = br.readLine().split(" ");
            String[] input2 = br.readLine().split(" ");

            int startX = Integer.parseInt(input1[0]);
            int startY = Integer.parseInt(input1[1]);
            int endX = Integer.parseInt(input2[0]);
            int endY = Integer.parseInt(input2[1]);

            Pair start = new Pair(startX, startY, 0);
            visited[startY][startX] = true;

            Queue<Pair> q = new LinkedList<>();
            q.add(start);


            while(true) {
                Pair polledPair = q.poll();
                if(polledPair.x==endX && polledPair.y==endY) {
                    outputList.add(polledPair.dist);
                    break;
                }

                for(int j=0; j<8;j++) {
                    int nx = polledPair.x + dx[j];
                    int ny = polledPair.y + dy[j];

                    if(nx <0 || ny<0 || nx>=l || ny>=l) continue;
                    if(visited[ny][nx] == true) continue;

                    visited[ny][nx] = true;
                    q.add(new Pair(nx, ny,polledPair.dist+1));
                }

            }

        }
        for(int i:outputList) {
            System.out.println(i);
        }

    }


    static class Pair{
        int x;
        int y;
        int dist;

        Pair(int x, int y, int dist){
            this.x = x;
            this.y = y;
            this.dist = dist;
        }
    }

}

 

나이트가 이동한 거리 횟수를 확인하기 위해 Pair 클래스에 dist 변수를 추가한다.

맨 처음 큐에 들어가는 시작점 Pair의 dist는 0으로 정한다.

이후 큐가 이동 가능한 거리를 실제로 이동했을 때 해당 좌표에 대해 Pair을 선언하며 기존의 Pair.dist에서 1을 더해준다.

q.add(new Pair(nx, ny,polledPair.dist+1));