BOJ 7562 나이트의 이동

www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

접근

1. 나이트가 갈 수 있는 곳을 bfs로 돌면서 목표 지점에 도착하면 이동 횟수 최솟값 반환

 

풀이

1. 테스트 케이스 마다 판의 크기, 시작 지점, 목표 지점을 입력받는다.
2. bfs 메소드를 호출한다.
3. dy, dx에 나이트가 이동할 수 있는 경우의 수를 지정한다.
4. 시작지점을 큐에 넣고 나이트가 이동할 수 있는 곳을 bfs로 순회한다.

 

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

class Main {
    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    static class Point{
        int y;
        int x;
        int count;

        public Point(int y, int x, int count) {
            this.y = y;
            this.x = x;
            this.count = count;
        }

        public Point(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    static int N;
    public static void main(String[] args) throws Exception {
    
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = stoi(br.readLine());
        for (int i = 0; i < N; i++) {
            int M = stoi(br.readLine());
            
            st = new StringTokenizer(br.readLine());
            Point start = new Point(stoi(st.nextToken()), stoi(st.nextToken()), 0);
            
            st = new StringTokenizer(br.readLine());
            Point target = new Point(stoi(st.nextToken()), stoi(st.nextToken()));

            System.out.println(bfs(start, target, M));
        }
    }

    static int bfs(Point start, Point target, int M){
        int[] dy = new int[]{-1, -2, -2, -1, 1, 2, 2, 1};
        int[] dx = new int[]{-2, -1, 1, 2, 2, 1, -1, -2};

        Queue<Point> q = new LinkedList();
        boolean[][] visited = new boolean[M][M];
        visited[start.y][start.x] = true;

        q.add(start);
        int answer = 987654321;
        
        while(!q.isEmpty()){
            Point current = q.poll();
            
            if(current.y == target.y && current.x == target.x){
                answer = Math.min(answer, current.count);
                continue;
            }
            
            for (int i = 0; i < 8; i++) {
                int nextY = current.y + dy[i];
                int nextX = current.x + dx[i];
                if(nextY >= M || nextY < 0 || nextX >= M || nextX < 0 || visited[nextY][nextX]) continue;
                visited[nextY][nextX] = true;
                q.add(new Point(nextY, nextX, current.count+1));
            }
        }

        return answer;
    }
}