[코드트리 챌린지] 나이트

문제

https://www.codetree.ai/cote/13/problems/knight-movements?&utm_source=clipboard&utm_medium=text

풀이방법

• 우선 나이트가 이동할 수 있는 곳을 dx, dy 테크닉을 사용하여 미리 정해주었다.
• 그리고 출발점을 기준으로 bfs를 돌렸는데, 이때 주의할 점이 갈 수 없는 곳은 -1을 출력해주어야하기 때문에 처음 dist 배열을 -1로 초기화해주었다. (1,1)에서 (1,1)로 방문하면 0이어야 하기 때문

코드

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

public class Main {
    static int n;
    static boolean[][] visited;
    static int[] dx = {-1, -2, -1, -2, 1, 2, 1, 2}; // 나이트가 갈 수 있는 장소 좌표 설정
    static int[] dy = {2, 1, -2, -1, 2, 1, -2, -1};
    static int[][] dist;
    static class Pair { // 좌표를 담을 자료형
        int x, y;

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

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

        n = Integer.parseInt(br.readLine());

        dist = new int[n + 1][n + 1]; // 거리 배열 초기화
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dist[i][j] = -1;
            }
        }
        visited = new boolean[n + 1][n + 1];

        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
        int r1 = Integer.parseInt(stk.nextToken()); // 시작점
        int c1 = Integer.parseInt(stk.nextToken());
        int r2 = Integer.parseInt(stk.nextToken()); // 도착점
        int c2 = Integer.parseInt(stk.nextToken());

        bfs(r1, c1);
        
        if (dist[r2][c2] == -1) {
            System.out.println(-1);
        } else {
            System.out.println(dist[r2][c2]);
        }
    }

    private static void bfs(int r1, int c1) {
        Queue<Pair> q = new LinkedList<>();
        q.offer(new Pair(r1, c1));
        visited[r1][c1] = true;
        dist[r1][c1] = 0;

        while (!q.isEmpty()) {
            Pair cur = q.poll();
            for (int dir = 0; dir < 8; dir++) {
                int nr = cur.x + dx[dir];
                int nc = cur.y + dy[dir];
                if (nr <= 0 || nc <= 0 || nr > n || nc > n) {
                    continue;
                }
                if (visited[nr][nc]) {
                    continue;
                }
                visited[nr][nc] = true;
                dist[nr][nc] = dist[cur.x][cur.y] + 1;
                q.offer(new Pair(nr, nc));
            }
        }
    }
}

느낀점

오늘 코테시험을 보느라 진이 빠져서 공부를 많이 하지 못했다. 내일도 코딩테스트를 보는데 내일부터는 힘을내서 공부해야겠다.
추가로, 오늘 코테에서 4문제 중 2문제를 풀었는데, (맞는지는 모른다..) 완탐 문제를 뇌정지가 오지 않고 풀었다면 3문제를 풀어서 제출할 수 있었는데.. 생각보다 완탐이 약한가보다. 보완을 해야할 것 같다.