[Java] 백준 BOJ / 7562번: 나이트의 이동

나이트의 이동

문제

---

문제 설명

체스의 나이트의 초기 위치와 목적 위치가 주어졌을 때 나이트가 최소 몇 번 만에 이동할 수 있는지를 구하는 문제이다.

최소거리를 구해야하니 이번엔 BFS를 사용해서 구현하기로 하였다.

BFS로 구하면 최단거리를 정확하게 계산할 수 있다.

BFS 에서는 Queue를 이용해서 가까운 노드부터 계산하고 같은 레벨의 노드를 먼저 탐색하기 때문에 최단거리를 보장한다.

일단 좌표들을 관리하기 위한 Point 클래스를 만들었다.

public static class Point {
	int x;
	int y;

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

그 후 나이트의 초기 위치와 마지막 위치를 Point 타입 변수로 저장한 후 시작위치부터 BFS를 돌고 한 칸씩 이동할 때마다 이전 좌표까지의 값에 1을 더한 값을 arr 배열에 넣어주면 된다.

public static void bfs() {
	Queue<Point> queue = new LinkedList<>();
	queue.add(new Point(startX, startY));
	visited[startX][startY] = true;
	while (!queue.isEmpty()) {
		Point cur = queue.poll();
		for (int i = 0; i < 8; i++) {
       		int nx = cur.x + dx[i];
			int ny = cur.y + dy[i];
			if (nx >= 0 && nx < l && ny >= 0 && ny < l) {
				if (!visited[nx][ny]) {
					visited[nx][ny] = true;
					arr[nx][ny] = arr[cur.x][cur.y] + 1;
					queue.add(new Point(nx, ny));
				}
			}
		}
	}
}

위의 조건들을 모두 만족시키는 것을 bfs 함수로 만들면 위의 코드와 같다.

최종 출력 값은 기존에 입력으로 받았던 목적지 값인 arr[endX][endY] 값을 출력해주면 되는 문제이다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_7562 {
    static int testCase;
    static int l;
    static int[][] arr;
    static int startX, startY, endX, endY;
    static Point start, end;
    static int[] dx = {-1, -2, -1, -2, 1, 2, 1, 2};
    static int[] dy = {2, 1, -2, -1, 2, 1, -2, -1};
    static boolean[][] visited;

    public static class Point {
        int x;
        int y;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        testCase = Integer.parseInt(br.readLine());

        for (int t = 0; t < testCase; t++) {
            l = Integer.parseInt(br.readLine());
            arr = new int[l][l];
            visited = new boolean[l][l];

            StringTokenizer st = new StringTokenizer(br.readLine());

            startX = Integer.parseInt(st.nextToken());
            startY = Integer.parseInt(st.nextToken());

            start = new Point(startX, startY);

            st = new StringTokenizer(br.readLine());

            endX = Integer.parseInt(st.nextToken());
            endY = Integer.parseInt(st.nextToken());

            end = new Point(endX, endY);

            bfs();

            System.out.println(arr[endX][endY]);
        }
    }

    public static void bfs() {
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(startX, startY));
        visited[startX][startY] = true;
        while (!queue.isEmpty()) {
            Point cur = queue.poll();
            for (int i = 0; i < 8; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];

                if (nx >= 0 && nx < l && ny >= 0 && ny < l) {
                    if (!visited[nx][ny]) {
                        visited[nx][ny] = true;
                        arr[nx][ny] = arr[cur.x][cur.y] + 1;
                        queue.add(new Point(nx, ny));
                    }
                }
            }
        }
    }
}