알고리즘 풀이 - 백준 7562(나이트의 이동, 그래프(BFS))

 

관련글

 

그래프 관련 포스팅은 여기를 참조
DFS 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

IxI 크기의 체스판 위 특정 위치에 나이트가 있을 때, 나이트가 이동하여 주어진 위치로 최소의 경우로 이동할 수 있는 움직임의 수를 구하는 문제

 

 

2. 풀이

 

이 문제는 나이트가 이동하며 특정 위치로 도달하기 위한 최소 이동 경로를 찾는 문제이다.

최소 이동 경로를 찾을 때는 DFS를 통해서 수행하면 최소의 경우를 보장할 수 없어 BFS 탐색을 통해 문제를 해결해보자.

 

BFS 탐색은 모든 인접 정점을 최소 이동 횟수로 보장해주는 탐색 방식이다. 현재 정점 위치를 저장하고 그 위치에서 8개의 방향으로 이동하며 목표 지점을 찾을 때까지 탐색을 수행하면 된다.

각 정점으로 이동했을 때, 이동 횟수를 저장하는 배열을 따로 생성하여 그 내역을 저장하고 목표 지점을 찾으면 추가 탐색을 멈추고 해당 이동 횟수를 바로 출력한다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        int t = Integer.parseInt(st.nextToken());
        while(t-- > 0){
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken());
            int[][] chess = new int[i][i];
            int[][] move = new int[i][i];

            // 최초 위치 부분을 Queue에 삽입
            Queue<Knight> q = new LinkedList<>();
            st = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            q.offer(new Knight(y, x));

            // 목표 위치 저장
            st = new StringTokenizer(br.readLine());
            int dest_y = Integer.parseInt(st.nextToken());
            int dest_x = Integer.parseInt(st.nextToken());

            // 인접한 경로를 이동하여 최단 경로를 찾는다.
            while(!q.isEmpty()){
                Knight now = q.poll();
                int cy = now.y;
                int cx = now.x;

                for(int k=0; k < 8; k++){
                    int ny = cy + dy[k];
                    int nx = cx + dx[k];

                    // 최초 위치로 돌아가는 경우는 넘어가야함.
                    if(ny == y && nx == x) continue;
                    
                    // 범위 안에 있고 이전에 탐색하지 않은 경우 탐색 수행
                    if(0 <= ny && ny < i && 0 <= nx && nx < i && move[ny][nx] == 0){
                        move[ny][nx] = move[cy][cx] + 1;
                        q.offer(new Knight(ny, nx));
                    }
                }
                // 목표 지점에 다다랐다면 추가 탐색이 불 필요
                if(move[dest_y][dest_x] != 0) break;
            }
            System.out.println(move[dest_y][dest_x]);
        }

        br.close();
    }
}

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

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.