[백준] 7562_ 나이트의이동 / 그래프, 최단경로, BFS

 

 

Sliver

 

 

문제

 

체스판 위에 한 나이트가 놓여져 있다.

나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다.

나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

 

 

입력

 

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다.

첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다.

체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다.

둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

 

 

출력

 

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

 

 

 

---

 

풀이

 

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        
        for(int i=0; i<N; i++){
            int l = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());
            int result = bfs(l, x1, y1, x2, y2);
            sb.append(result).append("\n");
        }
        System.out.println(sb); 
    }

    public static int bfs(int l, int sx, int sy, int ex, int ey){
        Queue<int[]> q = new LinkedList<>();
        int[][] map = new int[l][l];
        q.offer(new int[] {sx, sy});
        
        int[] dx = {2, 2, -2,-2, 1, 1, -1, -1};
        int[] dy = {1,-1, -1, 1, 2,-2,  2, -2};
        
        while(!q.isEmpty()){
           int[] now = q.poll();
            int xx = now[0];
            int yy = now[1];
            if(xx==ex && yy==ey) return map[xx][yy];
            
            for(int i=0; i<8; i++){
                int nx = xx+dx[i];
                int ny = yy+dy[i];
                if(nx >= 0 && nx < l && ny >=0 && ny < l && map[nx][ny] == 0){
                    map[nx][ny] = map[xx][yy]+1;
                    q.offer(new int[] {nx,ny});
                }
            }
            
            /*
            if(xx+2>=0 && xx+2<l && yy+1 >=0 && yy+1<l && map[xx+2][yy+1]==0){
                map[xx+2][yy+1] = map[xx][yy]+1;
                q.offer(new int[] {xx+2, yy+1});
            }
            if(xx+2>=0 && xx+2<l && yy-1 >=0 && yy-1<l && map[xx+2][yy-1]==0){
                map[xx+2][yy-1] = map[xx][yy]+1;
                q.offer(new int[] {xx+2, yy-1});
            }
            if(xx+1>=0 && xx+1<l && yy+2 >=0 && yy+2<l && map[xx+1][yy+2]==0){
                map[xx+1][yy+2] = map[xx][yy]+1;
                q.offer(new int[] {xx+1, yy+2});
            }
            if(xx-1>=0 && xx-1<l && yy+2 >=0 && yy+2<l && map[xx-1][yy+2]==0){
                map[xx-1][yy+2] = map[xx][yy]+1;
                q.offer(new int[] {xx-1, yy+2});
            }
            
            if(xx-2>=0 && xx-2<l && yy+1 >=0 && yy+1<l && map[xx-2][yy+1]==0){
                map[xx-2][yy+1] = map[xx][yy]+1;
                q.offer(new int[] {xx-2, yy+1});
            }
            if(xx-2>=0 && xx-2<l && yy-1 >=0 && yy-1<l && map[xx-2][yy-1]==0){
                map[xx-2][yy-1] = map[xx][yy]+1;
                q.offer(new int[] {xx-2, yy-1});
            }
            if(xx+1>=0 && xx+1<l && yy-2 >=0 && yy-2<l && map[xx+1][yy-2]==0){
                map[xx+1][yy-2] = map[xx][yy]+1;
                q.offer(new int[] {xx+1, yy-2});
            }
            if(xx-1>=0 && xx-1<l && yy-2 >=0 && yy-2<l && map[xx-1][yy-2]==0){
                map[xx-1][yy-2] = map[xx][yy]+1;
                q.offer(new int[] {xx-1, yy-2});
            }
            
            */
        }
        return -1;
    }
    
}

 

 

 

해결방법

• 체스판 크기 I 와 시작좌표(sx, sy) 도착좌표(ex, ey) 를 입력받는다. 
• 얻은 정보를 바탕으로 BFS 탐색을 시작한다
  1. 나이트의 이동 횟수를 기록하기 위해 map 배열을 생성한다.
  2. 이동 위치가 체스판 내부이고 방문한 적이 없다면, map 배열을 업데이트하고 큐에 추가한다.
  3. 현재위치가 도착위치가 되었다면 이동 횟수를 반환한다.

 

사용기술

• BFS (너비 우선 탐색): 최단 경로 탐색을 위해 사용
• Queue 자료구조: BFS에서 현재 위치의 인접한 위치를 순차적으로 처리하기 위해 사용

 

BFS를 사용한 이유

• BFS는 한번에 한 레벨씩 탐색하므로, 가장 먼저 도착한 경로가 최단경로임을 보장한다. 

 

 

 

 

---

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