7562_나이트의 이동

사용 알고리즘: bfs

사용 언어: java

 

package src.alStudy02;

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 *  1. 처음에 visited 배열 없이 했음
 *  2. 맵 사이즈가 100만 되도 답이 안 나옴
 *   ㄴ 맵을 copy하는 거 어디서 해야 할지 감이 안 잡혀서 copy해야 되는 걸 별로 안 좋아함
 *   ㄴ 해결: Knight 클래스를 만든 김에 거기에 visited 배열을 만들기로 함
 *   ㄴ 결과: 짜잔~!
 */

public class Main_bj_7562_나이트의이동 {
    static int I;
    static int[][] map;
    static int[] dx = {-1,-2,-2,-1,1,2,2,1};
    static int[] dy = {-2,-1,1,2,-2,-1,1,2};

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

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

        //테스트 케이스 돌기
        for (int t = 0; t < test; t++) {
            I = Integer.parseInt(br.readLine());
            map = new int[I][I];

            st = new StringTokenizer(br.readLine());
            Point startP = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

            st = new StringTokenizer(br.readLine());
            Point endP = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

            bfs_7562(startP, endP);
        }
        //
    }

    private static void bfs_7562(Point startP, Point endP) {
        Queue<Knight> q = new ArrayDeque<>();
        boolean[][] visited = new boolean[I][I];
        visited[startP.x][startP.y] = true;
        q.offer(new Knight(startP, 0, visited)); //현재 위치, 이동 횟수

        while (!q.isEmpty()) {
            Knight knight = q.poll();

            //종착점으로 오면 카운트 뱉고 끝
            if(knight.point.x == endP.x && knight.point.y == endP.y) {
                System.out.println(knight.moveCnt);
                return;
            }

            for (int d = 0; d < 8; d++) {
                int nx = dx[d] + knight.point.x;
                int ny = dy[d] + knight.point.y;

                if(nx>=0 && nx<I && ny>=0 && ny<I && !knight.visited[nx][ny]) {
                    knight.visited[nx][ny] = true;
                    q.offer( new Knight( new Point(nx, ny), knight.moveCnt+1, knight.visited ) );
                }
            }
        }
        //
    }
}

class Knight {
    Point point;
    int moveCnt;
    boolean[][] visited;

    public Knight(Point point, int moveCnt, boolean[][] visited) {
        this.point = point;
        this.moveCnt = moveCnt;
        this.visited = visited;
    }
}

 

 

인사이트: 

1. 처음에 visited 배열 없이 했음
*  2. 맵 사이즈가 100만 되도 답이 안 나옴
*   ㄴ 맵을 copy하는 거 어디서 해야 할지 감이 안 잡혀서 copy해야 되는 걸 별로 안 좋아함
*   ㄴ 해결: Knight 클래스를 만든 김에 거기에 visited 배열을 만들기로 함
*   ㄴ 결과: 짜잔~!