[백준 7562] 나이트의 이동 (C#, C++) - soo:bak

문제 링크

7562번 - 나이트의 이동

설명

체스판 위의 나이트가 현재 위치에서 목표 위치까지 이동할 때, 최소 몇 번의 이동이 필요한지 구하는 문제입니다. 각 테스트 케이스마다 체스판 크기와 시작 좌표, 도착 좌표가 주어집니다.

접근법

나이트의 한 번 이동은 항상 비용이 1로 같으므로, 최단 이동 횟수는 너비 우선 탐색(BFS) 으로 구할 수 있습니다.

시작 칸에서 BFS를 시작하면, 먼저 방문하는 칸일수록 더 적은 횟수로 도달한 칸입니다. 따라서 목표 칸에 처음 도달했을 때의 거리가 곧 정답입니다.

나이트는 다음 8가지 방향으로 이동할 수 있습니다.

• (-2, -1), (-2, 1)
• (-1, -2), (-1, 2)
• (1, -2), (1, 2)
• (2, -1), (2, 1)

각 테스트 케이스마다 거리 배열을 -1로 초기화한 뒤, 아직 방문하지 않은 칸만 큐에 넣어 탐색하면 됩니다.

---

Code

C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Program {
  static readonly int[] dx = { -2, -2, -1, -1, 1, 1, 2, 2 };
  static readonly int[] dy = { -1, 1, -2, 2, -2, 2, -1, 1 };

  static void Main() {
    int t = int.Parse(Console.ReadLine()!);
    var sb = new StringBuilder();

    while (t-- > 0) {
      int l = int.Parse(Console.ReadLine()!);
      int[] start = Console.ReadLine()!.Split().Select(int.Parse).ToArray();
      int[] target = Console.ReadLine()!.Split().Select(int.Parse).ToArray();

      if (start[0] == target[0] && start[1] == target[1]) {
        sb.AppendLine("0");
        continue;
      }

      int[,] dist = new int[l, l];
      for (int i = 0; i < l; i++) {
        for (int j = 0; j < l; j++) {
          dist[i, j] = -1;
        }
      }

      var q = new Queue<(int x, int y)>();
      q.Enqueue((start[0], start[1]));
      dist[start[0], start[1]] = 0;

      while (q.Count > 0) {
        var cur = q.Dequeue();

        if (cur.x == target[0] && cur.y == target[1])
          break;

        for (int dir = 0; dir < 8; dir++) {
          int nx = cur.x + dx[dir];
          int ny = cur.y + dy[dir];

          if (nx < 0 || nx >= l || ny < 0 || ny >= l)
            continue;
          if (dist[nx, ny] != -1)
            continue;

          dist[nx, ny] = dist[cur.x, cur.y] + 1;
          q.Enqueue((nx, ny));
        }
      }

      sb.AppendLine(dist[target[0], target[1]].ToString());
    }

    Console.Write(sb.ToString());
  }
}

C++

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

int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};

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

  int t;
  cin >> t;

  while (t--) {
    int l;
    cin >> l;

    int sx, sy, tx, ty;
    cin >> sx >> sy;
    cin >> tx >> ty;

    if (sx == tx && sy == ty) {
      cout << 0 << "\n";
      continue;
    }

    vector<vector<int>> dist(l, vector<int>(l, -1));
    queue<pair<int, int>> q;
    q.push({sx, sy});
    dist[sx][sy] = 0;

    while (!q.empty()) {
      auto cur = q.front();
      q.pop();

      if (cur.first == tx && cur.second == ty)
        break;

      for (int dir = 0; dir < 8; dir++) {
        int nx = cur.first + dx[dir];
        int ny = cur.second + dy[dir];

        if (nx < 0 || nx >= l || ny < 0 || ny >= l)
          continue;
        if (dist[nx][ny] != -1)
          continue;

        dist[nx][ny] = dist[cur.first][cur.second] + 1;
        q.push({nx, ny});
      }
    }

    cout << dist[tx][ty] << "\n";
  }

  return 0;
}