[백준] 7562번 - 나이트의 이동 풀이 및 코드 분석 (Java)

문제 링크

1. 문제 분석

🏰 문제 개요

체스판 위에서 나이트(knight)가 주어진 위치에서 목표 위치까지 이동하는 최소 횟수를 구하는 문제이다.
나이트는 다음과 같은 8가지 방향으로 이동할 수 있다.

(-1, -2), (-2, -1), (-2, 1), (-1, 2), 
(1, -2), (2, -1), (2, 1), (1, 2)

🎯 요구사항

1. 나이트가 l x l 크기의 체스판에서 이동해야 한다.
2. 출발 위치 (sr, sc)에서 도착 위치 (er, ec)까지 가는 최소 이동 횟수를 구해야 한다.
3. 여러 개의 테스트 케이스가 주어지므로, 각각의 결과를 출력해야 한다.

---

2. 해결 방법

🔹 핵심 개념

이 문제는 그래프 탐색(BFS)를 이용하면 최적의 해결책을 찾을 수 있다.
BFS는 최단 경로를 찾을 때 가장 적합한 알고리즘이다.

🔑 해결 절차

1. 입력값 처리 및 체스판 초기화
   • 체스판의 크기 l을 입력받고, 이동해야 할 출발 위치와 도착 위치를 입력받는다.
   • 최소 이동 횟수를 저장할 board[][] 배열을 Integer.MAX_VALUE로 초기화한다.
2. BFS 탐색을 수행하여 최단 거리 찾기
   • 시작점을 큐에 넣고, 이동할 수 있는 8가지 방향으로 탐색한다.
   • 방문하지 않은 좌표라면, 이동 횟수를 업데이트하고 큐에 추가한다.
   • 도착 위치에 도달하면 탐색을 종료한다.
3. 최소 이동 횟수를 출력
   • board[er][ec] 값을 출력하면 최소 이동 횟수를 얻을 수 있다.

---

3. 코드 구현

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

public class Main {
    static int l, sr, sc, er, ec;
    static int[] dr = {-1, -2, -2, -1, 1, 2, 2, 1};
    static int[] dc = {-2, -1, 1, 2, 2, 1, -1, -2};
    static int[][] board;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 개수

        for (int t = 0; t < T; t++) {
            l = Integer.parseInt(br.readLine()); // 체스판 크기
            board = new int[l][l];

            for (int i = 0; i < l; i++) {
                Arrays.fill(board[i], Integer.MAX_VALUE);
            }

            StringTokenizer st = new StringTokenizer(br.readLine());
            sr = Integer.parseInt(st.nextToken());
            sc = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            er = Integer.parseInt(st.nextToken());
            ec = Integer.parseInt(st.nextToken());

            System.out.println(bfs());
        }
    }

    // BFS 탐색
    private static int bfs() {
        Queue<int[]> q = new LinkedList<>();
        boolean[][] visited = new boolean[l][l];

        q.add(new int[] {sr, sc});
        visited[sr][sc] = true;
        board[sr][sc] = 0;

        while (!q.isEmpty()) {
            int[] current = q.poll();
            int r = current[0], c = current[1];

            // 목표 지점 도착 시 최소 이동 횟수 반환
            if (r == er && c == ec) {
                return board[r][c];
            }

            for (int d = 0; d < 8; d++) {
                int nr = r + dr[d];
                int nc = c + dc[d];

                if (isValid(nr, nc, visited)) {
                    q.add(new int[] {nr, nc});
                    visited[nr][nc] = true;
                    board[nr][nc] = board[r][c] + 1;
                }
            }
        }
        return -1;
    }

    // 이동 가능 여부 체크
    private static boolean isValid(int r, int c, boolean[][] visited) {
        return r >= 0 && r < l && c >= 0 && c < l && !visited[r][c];
    }
}

---

4. 코드 분석

🔹 주요 알고리즘

1. 입력 처리 & 체스판 초기화
   • board[][] 배열을 Integer.MAX_VALUE로 설정하여 최소 이동 횟수를 저장할 공간을 만든다.
   • 테스트 케이스마다 새로운 체스판을 생성한다.
2. BFS 탐색을 이용한 최단 경로 찾기
   • Queue<int[]>를 활용하여 시작점을 sr, sc로 설정하고 탐색을 시작한다.
   • 나이트가 이동할 수 있는 8가지 방향을 탐색하면서 board[][]에 이동 횟수를 저장한다.
   • visited[][]를 활용하여 방문한 곳을 체크하고, 중복 방문을 방지한다.
   • 목표 지점 (er, ec)에 도착하면 현재 board[er][ec] 값을 반환한다.
3. 출력 처리
   • 모든 테스트 케이스에 대해 최소 이동 횟수를 출력한다.

---

5. 개선할 점 및 대체 방법

✅ 개선할 점

1. board[][]를 visited[][]로 대체 가능
   • 현재 board[][]를 사용해 이동 횟수를 저장하지만, visited[][]만 사용해도 충분하다.
   • board[][] 없이 int[][] dist를 사용하면 공간 절약이 가능하다.
2. PriorityQueue를 활용한 최적화 가능
   • 이 문제에서는 일반적인 BFS로 해결 가능하지만, 우선순위 큐 (Dijkstra 알고리즘)를 활용하면 더욱 최적화할 수 있다.

🔄 대체 방법

1. DFS 사용 불가능
   • DFS는 최단 경로를 보장하지 않기 때문에 적절한 방법이 아니다.
   • BFS는 최단 거리 탐색에 적합하다.
2. Bidirectional BFS 적용 가능
   • 양쪽에서 탐색하는 Bidirectional BFS를 사용하면 연산 횟수를 절반으로 줄일 수 있다.