[백준] 7562번 - 나이트의 이동 [Java]

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

 

[백준] 7562번 - 나이트의 이동 [Java]

[백준] 7562번 - 나이트의 이동 [Java]

---

1.  아이디어

 

최단거리를 구하는 문제로 BFS를 활용하면 해결할 수 있다.

---

2. 문제풀이

 

2차원 배열과 BFS에서 일반적으로 사용하는 사방탐색 배열 대신 나이트의 이동에 맞게 8칸 이동을 할 수 있게 구현만 하면 됐다. BFS에서 최단 거리는 Queue의 크기를 변수에 담아 해당 변수만큼 반복하면 1칸 이동을 체크할 수 있다.

---

3. 코드

 

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

public class Main {

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

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

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

        for (int tc = 1; tc <= T; tc++) {
            int L = Integer.parseInt(br.readLine());

            st = new StringTokenizer(br.readLine());
            int r1 = Integer.parseInt(st.nextToken());
            int c1 = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            int r2 = Integer.parseInt(st.nextToken());
            int c2 = Integer.parseInt(st.nextToken());

            int cnt = bfs(r1, c1, r2, c2, L);
            sb.append(cnt).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
    }

    private static int bfs(int r1, int c1, int r2, int c2, int L) {
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{r1, c1});

        boolean[][] visited = new boolean[L][L];
        visited[r1][c1] = true;

        int dist = 0;

        while (!q.isEmpty()) {
            int len = q.size();

            for (int i = 0; i < len; i++) {
                int[] item = q.poll();
                if (item[0] == r2 && item[1] == c2) return dist;

                for (int dir = 0; dir < 8; dir++) {
                    int nr = item[0] + dr[dir];
                    int nc = item[1] + dc[dir];

                    if (nr < 0 || nr >= L || nc < 0 || nc >= L) continue;
                    if (visited[nr][nc]) continue;

                    q.offer(new int[]{nr, nc});
                    visited[nr][nc] = true;
                }
            }

            dist++;
        }

        return -1;
    }

}

---

4. 후기