[백준(JAVA)] 7562번: 나이트의 이동

문제

✔ 난이도 - Silver 1

설명

bfs - 최단거리

나이트가 한 번에 움직일 수 있는 거리는 (r, c)으로 보면
(-2, 1) (-1, 2) (1, 2) (2, 1) (2, -1) (1, -2) (-1, -2) (-2, -1) 이다

저 순서대로 돌면서 bfs로 목표지점 최단거리 찾기

풀이

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        while(T-- > 0){
            int I = Integer.parseInt(br.readLine());
            boolean[][] visited = new boolean[I][I];
            
            String[] current = br.readLine().split(" ");
            String[] target = br.readLine().split(" ");

            int curR = Integer.parseInt(current[0]);
            int curC = Integer.parseInt(current[1]);
            int targetR = Integer.parseInt(target[0]);
            int targetC = Integer.parseInt(target[1]);

            int[] dr = {-2, -1, 1, 2, 2, 1, -1, -2};
            int[] dc = {1, 2, 2, 1, -1, -2, -2, -1};

            sb.append(bfs(visited, curR, curC, targetR, targetC, dr, dc, I)).append("\n");
        }
        
        System.out.println(sb);
    }

    private static int bfs(boolean[][] visited, int curR, int curC, int targetR, int targetC, int[] dr, int[]dc, int I) {
        Queue<int[]> queue = new LinkedList<>();
        int count = 0;

        queue.offer(new int[] {curR, curC, count});
        visited[curR][curC] = true;

        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            int cr = node[0];
            int cc = node[1];
            count = node[2];

            if (cr == targetR && cc == targetC){
                return count;
            }

            for (int i = 0; i < 8; i++){
                int nr = cr + dr[i];
                int nc = cc + dc[i];

                if (nr < 0 || nc < 0 || nr > I-1 || nc > I-1 || visited[nr][nc] == true) continue;

                queue.offer(new int[] {nr, nc, count + 1});
                visited[nr][nc] = true;
            }
        }

        return 0;
    }
}

⏰ 시간복잡도

$O(N^2)$