99클럽 코테 스터디 9일차 TIL

백준 - 7562번

문제 키워드

• 나이트가 특정 지점에서부터 이동할 수 있는 칸 수는 최대 8칸이다.
• 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

주어진 체스판 안에서 나이트가 이동할 수 있는 모든 지점을 방문해야 한다.

현재 지점에서 나이트가 이동할 수 있는 최대 8개 지점을 계산하고, 한 지점씩 방문한다. 

방문하지 않은 지점을 queue에 저장하고,

방문할 때마다 현재 방문지점이 시작지점에서 몇 번 이동해야 도착할 수 있는지 기록한다.

 

작은 범위의 체스판을 그려 이해해보자.

체스판 : 4 * 4

시작지점 : 0, 0

목표지점 : 3, 0

start	3	2	5
3	4	1	2
2	1	4	3
end 5	2	3	2

실제 코드에서는 목표지점에 도착했다하더라도 모든 지점을 탐색한다.

하지만 목표지점은 이미 방문했기 때문에 숫자는 변경되지 않는다.

 

BFS 가 종료되면 체스판의 각 지점에 숫자가 채워진다.

테스트 케이스마다 BFS를 수행하고 체스판의 목표지점을 출력하면 된다.

---

구현

static 변수

static final int[] ROW_MOVE = {-2, -1, 1, 2, 2, 1, -1, -2};
static final int[] COL_MOVE = {1, 2, 2, 1, -1, -2, -2 ,-1};
static final int MOVE_COUNT = 8;
static int n; // 체스판 길이
static int[][] chessBoard; // 이중배열 체스판
static boolean[][] visited; // 체스판 방문여부

ROW_MOVE 와 COL_MOVE 의 경우, 나이트가 특정 지점에서 이동할 수 있는 지점을 계산하기 위해 설정한 값이다.

MOVE_COUNT는 나이트가 최대로 이동할 수 있는 칸 수이다. 굳이 설정해주지 않아도 되지만 매직넘버를 피하기 위해 설정했다.

	row - 2 col - 1		row - 2 col + 1
row - 1 col - 2				row - 1 col + 2
		spot
row + 1 col - 2				row + 1 col + 2
	row + 2 col - 1		row + 2 col + 1

 

main()

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    StringBuilder sb = new StringBuilder();

    int t = sc.nextInt();
    for (int i = 0; i < t; i++) {
        n = sc.nextInt();
        int startRow = sc.nextInt();
        int startCol = sc.nextInt();
        int endRow = sc.nextInt();
        int endCol = sc.nextInt();

        chessBoard = new int[n][n];
        visited = new boolean[n][n];

        bfs(startRow, startCol);

        sb.append(chessBoard[endRow][endCol]).append("\n");
    }

    System.out.println(sb);
    sc.close();
}

입력된 테스트 케이스와 여러 변수를 받아 체스판을 설정해준다.

bfs 함수가 종료되면 체스판의 모든 지점에 숫자가 채워지며,

테스트 케이스마다 목표지점의 숫자를 StringBuilder로 저장하고 반복문이 종료되면 결과값을 출력한다.

 

bfs 함수 및 Spot 클래스

static void bfs(int startRow, int startCol) {
    Queue<Spot> queues = new LinkedList<>();
    queues.add(new Spot(startRow, startCol));
    visited[startRow][startCol] = true;

    while (!queues.isEmpty()) {
        Spot spot = queues.remove();
        for (int i = 0; i < MOVE_COUNT; i++) {
            int row = spot.row;
            int col = spot.col;
            int newRow = row + ROW_MOVE[i];
            int newCol = col + COL_MOVE[i];

            if ((newRow >= 0 && newRow < n) && (newCol >= 0 && newCol < n)) {
                if (!visited[newRow][newCol]) {
                    visited[newRow][newCol] = true;
                    chessBoard[newRow][newCol] = chessBoard[row][col] + 1;
                    queues.add(new Spot(newRow, newCol));
                }
            }
        }
    }
}

static class Spot {
    public int row;
    public int col;

    public Spot(int row, int col) {
        this.row = row;
        this.col = col;
    }

}

나이트가 이동할 수 있는 지점을 계산하기 위해 특정 지점의 row, col 변수가 필요하다.

두 변수를 한번에 저장할 수 있는 Spot 객체를 만들어 queues에 저장했다.

---

백준 7562번 - 나이트의 이동

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