알고리즘 풀이 - 백준 16948(데스 나이트, 그래프(BFS))

 

관련글

 

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

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

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

 

체스의 데스 나이트를 새로 만들어서 이동이 가능할 때, NxN 체스판에서 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 횟수를 구하는 문제

 

 

2. 풀이

 

제일 간단한 수준의 BFS 문제이다. 각 이동 가능한 경우를 배열로 저장하고 이동 가능한 경우 이동시키면서 각 위치에 최소 이동 횟수를 저장하고 목표 지점에 도달하면 탐색을 중지하면 되는 문제이다.

 

쉬운 문제이므로 코드를 통해 이해하자.

 

 

3. 코드

 

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

 

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

public class Main{
    static int n;
    static int[][] chess;
    static boolean[][] visited;
    
    // 이동 가능 경로 저장
    static int[] dy = {-2, -2, 0, 0, 2, 2};
    static int[] dx = {-1, 1, -2, 2, -1, 1};
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        chess = new int[n+1][n+1];
        visited = new boolean[n+1][n+1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        int r1 = Integer.parseInt(st.nextToken());
        int c1 = Integer.parseInt(st.nextToken());
        int r2 = Integer.parseInt(st.nextToken());
        int c2 = Integer.parseInt(st.nextToken());

        // Queue를 통해 BFS 수행
        Queue<Pos> q = new LinkedList<>();
        q.offer(new Pos(r1, c1, 0));
        visited[r1][c1] = true;

        while(!q.isEmpty()){
            Pos c = q.poll();

            for(int i=0; i < 6; i++){
                int ny = c.y + dy[i];
                int nx = c.x + dx[i];

                // 범위를 벗어났거나 이미 방문 완료된 경우 넘어간다.
                if(ny < 0 || ny > n || nx < 0 || nx > n || visited[ny][nx]){
                    continue;
                }

                // 현재 위치가 목표 지점이라면 이동 횟수를 출력하고 종료한다.
                if(ny == r2 && nx == c2){
                    System.out.println(c.move + 1);
                    System.exit(0);
                }
                
                // 방문처리 후 다음에 탐색을 수행하도록 Queue에 넣는다.
                visited[ny][nx] = true;
                q.offer(new Pos(ny, nx, c.move+1));
            }
        }
        System.out.println(-1);
        br.close();
    }
}
class Pos{
    int y;
    int x;
    int move;
    public Pos(int y, int x, int move){
        this.y = y;
        this.x = x;
        this.move = move;
    }
}

 

 

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