[백준 JAVA] 7562 나이트의 이동

7562 나이트의 이동

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

문제설명

체스판의 크기와 여러 테스트 케이스에 대해 나이트가 시작점에서

목표점까지 이동하는 데 필요한 최소 이동 횟수를 계산한다.

접근방식

O(I^2)  시간복잡도

 

나이트는 최대 8방향으로 이동할 수 있다. 각 정점에서 최대 8개의 간선을 탐색할때 O(E) 의 BFS가 소요된다.

체스판의 크기가 I x I이므로 전체 정점의 수는 O(I^2)의 시간이 소요된다.

 

문제 조건 분석 과정

• 체스판: 크기가 I x I인 체스판이다.
• 나이트의 이동: 나이트는 8가지 방향으로 이동할 수 있다.
• 시작점을 큐에 추가하고, 방문 여부를 기록한다.
• 큐에서 위치를 꺼내며, 나이트의 모든 이동 가능 위치를 탐색한다.
• 각 이동에 대해 체스판의 경계와 방문 여부를 확인한다.
• 이동 횟수를 업데이트하고 목표점에 도달할 때까지 반복한다.

전체코드

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

public class Main {
    static int I; // 체스판의 크기 (I x I)
    static int x1, x2, y1, y2; // 시작점과 목표점의 좌표
    static int[][] arr; // 각 위치까지의 이동 횟수를 저장할 배열
    static boolean[][] visited; // 방문 여부를 저장할 배열
    static int[] dx = {1, 2, 2, 1, -1, -2, -2, -1}; // 나이트의 이동을 위한 x 방향
    static int[] dy = {2, 1, -1, -2, -2, -1, 1, 2}; // 나이트의 이동을 위한 y 방향

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

        for (int i = 1; i <= T; i++) {
            I = Integer.parseInt(br.readLine()); // 체스판의 크기 입력

            arr = new int[I][I]; // 각 위치까지의 이동 횟수를 저장할 배열 초기화
            visited = new boolean[I][I]; // 방문 여부를 저장할 배열 초기화

            st = new StringTokenizer(br.readLine());
            x1 = Integer.parseInt(st.nextToken()); // 시작점의 x 좌표
            y1 = Integer.parseInt(st.nextToken()); // 시작점의 y 좌표
            st = new StringTokenizer(br.readLine());
            x2 = Integer.parseInt(st.nextToken()); // 목표점의 x 좌표
            y2 = Integer.parseInt(st.nextToken()); // 목표점의 y 좌표

            bfs(); // 너비 우선 탐색 수행

            sb.append(arr[x2][y2]).append("\n");
        }
        System.out.println(sb); // 모든 테스트 케이스 결과를 출력
    }

    public static void bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x1, y1}); // 시작점을 큐에 추가
        visited[x1][y1] = true; // 시작점을 방문 처리

        while (!q.isEmpty()) {
            int[] now = q.poll(); // 큐에서 현재 위치를 꺼냄
            int nx = now[0];
            int ny = now[1];

            for (int i = 0; i < 8; i++) {
                int ox = nx + dx[i]; // 새로운 x 좌표 계산
                int oy = ny + dy[i]; // 새로운 y 좌표 계산

                // 새로운 좌표가 체스판 내에 있는지 확인
                if (ox >= 0 && oy >= 0 && ox < I && oy < I) {
                    if (!visited[ox][oy]) { // 해당 위치가 방문되지 않았으면
                        q.add(new int[]{ox, oy}); // 큐에 새로운 위치 추가
                        arr[ox][oy] = arr[nx][ny] + 1; // 이동 횟수 업데이트
                        visited[ox][oy] = true; // 새로운 위치 방문 처리
                    }
                }
            }
        }
    }
}