백준 7562번 나이트의 이동 - C++, SWIFT

문제

---

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

 

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

 

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

 

문제 링크

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

 

 

풀이

---

나이트의 이동 범위를 보면 하나씩 다 해봐야하나? 아니면 백트래킹? 이런저런 생각이 드는데 사실은 BFS를 사용하면 쉽게 해결할 수 있는 문제다.

 

예제를 보며 확인해보자.

8*8 체스판에 출발지가 `(0, 0)` 이고 목적지가 `(7, 0)`인 상황이라고 해보자. ▼

 

시작점에서 갈 수 있는 좌표를 큐에 넣는데, 큐에 넣을 때 한 가지 값을 하나 더 넣는다.

바로 해당 좌표까지 갈 수 있는 횟수인데, 현재 좌표까지 가는 최단 거리에 더하기 1을 해주면 된다. ▼

 

이번에는 방문하기 전에 방문했다고 체크를 미리 해놓는다.

그리고 다음에 이동할 때 방문이 체크되어있다면 큐에 넣지 않는다. ▼

 

그렇기에 실제로는 방문하지 않았지만, 미리 방문했다고 체크했기에 `(3, 3)`은 큐에 넣지 않게 된다. ▼

 

이 과정을 반복해준다. ▼

 

이 과정을 반복하다보면 체스판에 숫자가 오밀조밀 찍히게 되는데, 이 숫자들이 의미하는 것이 바로 시작지점부터 해당지점까지 이동하는 최단거리이다. ▼

 

그렇기에 목표 지점까지 도달할 때 까지 BFS를 계속 돌려주면 최단거리를 구할 수 있게 된다. ▼

 

 

SWIFT 코드

---

for _ in 0..<Int(readLine()!)! {
    let I = Int(readLine()!)!
    let K = readLine()!.split(separator: " ").map { Int(String($0))! }
    let D = readLine()!.split(separator: " ").map { Int(String($0))! }
    var V = Array(repeating: Array(repeating: false, count: I), count: I)
    let dy = [2, 1, -1, -2, -2, -1, 1, 2]
    let dx = [1, 2, 2, 1, -1, -2, -2, -1]
    var Q = [(Int, Int, Int)]()
    var index = 0

    Q.append((K[0], K[1], 0))
    V[K[0]][K[1]] = true
    while index < Q.count {
        let cur = Q[index]
        
        index += 1
        if cur.0 == D[0] && cur.1 == D[1] {
            print(cur.2)
            break
        }
        for i in 0..<8 {
            let y = cur.0 + dy[i]
            let x = cur.1 + dx[i]

            if y < 0 || y >= I || x < 0 || x >= I {
                continue
            }
            if V[y][x] == false {
                Q.append((y, x, cur.2 + 1))
                V[y][x] = true
            }
        }
    }
}

 

 

C++ 코드

---

#include <iostream>
#include <queue>
#include <algorithm>
#include <tuple>
#include <string.h>

using namespace std;

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

int T, l, sx, sy, ex, ey, answer;
int V[301][301];

void input() {
  cin >> l;
  cin >> sy >> sx;
  cin >> ey >> ex;
  answer = 0;
  for (int i = 0; i < 301; i++) {
    for (int j = 0; j < 301; j++) {
      V[i][j] = 0;
    }
  }
}

void BFS() {
  queue<tuple<int, int, int>> Q;

  Q.push({sy, sx, 0});

  V[sy][sx] = 1; 
  while (!Q.empty()) {
    tuple<int, int, int> cur = Q.front();
    Q.pop();

    
    if (get<0>(cur) == ey && get<1>(cur) == ex) {
      answer = get<2>(cur);
      break;
    }
    for(int i = 0; i < 8; i++) {
      int y = get<0>(cur) + dy[i];
      int x = get<1>(cur) + dx[i];

      if (y < 0 || y >= l || x < 0 || x >= l) {
        continue;
      }
      if (V[y][x] == 0) {
        Q.push({y, x, get<2>(cur) + 1});
        V[y][x] = 1;
      }
    }
  }
}

void output() {
  cout << answer << endl;
}

int main() {
  cin >> T;

  while (T--) {
    input();
    BFS();
    output();
  }
}

 

`endl`을 안붙여서 왜 계속 16%에서 틀리지...? 하고 계속계속 검증해봤다...