[BaekJoon] 7562번 - 나이트의 이동 [Java][C++]

문제 링크

---

1. 문제 풀이

나이트의 이동으로 목적지에 갈 수 있는 최소 횟수를 구하는 문제로 최단거리 BFS를 활용하면 해결할 수 있다. 일반적인 격자 그래프에서의 사방 탐색이 아닌 나이트의 이동 방법에 맞춘 팔방 탐색을 활용하면 된다.

---

2. 코드

1. 풀이 [Java]

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

public class Main {

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

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

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

            st = new StringTokenizer(br.readLine());
            int sr = Integer.parseInt(st.nextToken());
            int sc = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            int er = Integer.parseInt(st.nextToken());
            int ec = Integer.parseInt(st.nextToken());

            int dist = bfs(sr, sc, er, ec, len);
            sb.append(dist).append("\n");
        }

        System.out.print(sb);
    }

    static int bfs(int sr, int sc, int er, int ec, int len) {
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{sr, sc});

        boolean[][] visited = new boolean[len][len];
        visited[sr][sc] = true;

        int dist = 0;

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

            while (size-- > 0) {
                int[] node = q.poll();
                if (node[0] == er && node[1] == ec) return dist;

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

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

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

            dist++;
        }

        return -1;
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

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

bool visited[300][300];

int bfs(int sr, int sc, int er, int ec, int len) {
    queue<pair<int, int>> q;
    q.push({sr, sc});

    memset(visited, 0, sizeof(visited));
    visited[sr][sc] = true;

    int dist = 0;

    while (!q.empty()) {
        int sz = q.size();

        while (sz--) {
            auto [r, c] = q.front();
            q.pop();

            if (r == er && c == ec) return dist;

            for (int d = 0; d < 8; d++) {
                int nr = r + dr[d];
                int nc = c + dc[d];

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

                q.push({nr, nc});
                visited[nr][nc] = true;
            }
        }

        dist++;
    }

    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    for (int tc = 1; tc <= t; tc++) {
        int len, sr, sc, er, ec;
        cin >> len >> sr >> sc >> er >> ec;

        int dist = bfs(sr, sc, er, ec, len);
        cout << dist << '\n';
    }
}

---