문제 출처

단계별로 풀어보기 > 그래프와 순회 > 나이트의 이동
https://www.acmicpc.net/problem/7562

문제 설명

나이트의 시작 지점과 도착 지점이 주어질 때, 해당 위치로 이동하는 최소 이동 횟수를 출력하라.

접근 방법

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class 나이트의_이동 {
    static int[][] visited;

    static int[] dx = {1, 1, -1, -1, 2, 2, -2, -2};
    static int[] dy = {2, -2, 2, -2, 1, -1, 1, -1};

    public static void bfs(int startX, int startY, int targetX, int targetY){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{startX,startY});

        visited[startX][startY] = 1;

        while(!q.isEmpty()){
            int[] cur = q.poll();
            for(int i = 0; i < 8; i++){
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];

                if(nx < 0 || nx > visited.length-1 || ny < 0 || ny > visited[0].length-1) continue;
                if(visited[nx][ny] > 0) continue;
                q.add(new int[]{nx,ny});
                visited[nx][ny] = visited[cur[0]][cur[1]] + 1;
            }
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < T; i++){
            int l = Integer.parseInt(br.readLine());
            visited = new int[l][l];

            StringTokenizer st = new StringTokenizer(br.readLine());
            int cur[] = {Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};

            st = new StringTokenizer(br.readLine());
            int target[] = {Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};

            bfs(cur[0],cur[1],target[0],target[1]);
            sb.append(visited[target[0]][target[1]]-1).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();

    }
}

알게된 점

시간 복잡도는 최악일 경우 전체 배열을 다 지나가므로, O(l^2)이다.

문제푼 흔적