2023-04-03 BOJ 16948

문제 풀이 방식

• 이동 거리차가 2의 배수가 아니면 -1 리턴
• 정수 배열로 이동 가능한 거리 저장
• 이동 가능한 위치 저장하는 이차원 bool 배열 필요할듯?
• 최단거리니까 BFS로 푸는게 좋겟다

문제 풀이 (Java)

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.LinkedList;  
import java.util.Queue;  
import java.util.StringTokenizer;  
  
public class boj16948 {  
  
    static int n, r1, c1, r2, c2;  
    static boolean[][] visited;  
    static int[] dx = {-2, -2, 0, 0, 2, 2};  
    static int[] dy = {-1, 1, -2, 2, -1, 1};  
  
    static class knight {  
        // 현재 체스말 위치, 움직인 횟수 정보를 저장하는 클래스  
        int r;  
        int c;  
        int cnt;  
  
        public knight(int r, int c, int cnt) {  
            this.r = r;  
            this.c = c;  
            this.cnt = cnt;  
        }  
    }  
  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
  
        n = Integer.parseInt(br.readLine()); // 체스판 크기  
        StringTokenizer st = new StringTokenizer(br.readLine());  
        r1 = Integer.parseInt(st.nextToken());  
        c1 = Integer.parseInt(st.nextToken());  
        r2 = Integer.parseInt(st.nextToken());  
        c2 = Integer.parseInt(st.nextToken());  
        visited = new boolean[n][n];  
  
        System.out.println(bfs());  
    }  
  
    public static int bfs() {  
        Queue<knight> queue = new LinkedList<>();  
        queue.offer(new knight(r1, c1, 0));  
        visited[r1][c1] = true;  
  
        if (Math.abs(r2 - r1) % 2 == 1)  
            return -1;  
  
        while (!queue.isEmpty()) {  
            knight night = queue.poll();  
            // 현재 체스말의 위치가 찾고 있던 위치라면 cnt를 반환  
            if (night.r == r2 && night.c == c2) {  
                return night.cnt;  
            }  
  
            for (int i = 0; i < 6; i++) {  
                int newR = night.r + dx[i];  
                int newC = night.c + dy[i];  
                // 체스판 범위를 벗어나거나 이미 방문한 지점이라면 다음 경우의 수  
                if (newR < 0 || newR >= n || newC < 0 || newC >= n || visited[newR][newC]) {  
                    continue;  
                }  
  
                queue.offer(new knight(newR, newC, night.cnt + 1));  
                visited[newR][newC] = true;  
            }  
        }  
  
        return -1;  
    }  
}