[BOJ] 7562 - 나이트의 이동

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

BOJ - 나이트의 이동

문제 유형: bfs, 그래프, 최단 경로

문제 난이도: Silver I

시간 제한: 1초

메모리 제한: 256MB

 

문제

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

 

입력

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

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

 

출력

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

 

풀이

나이트의 이동을 별도로 저장해둔다.

나이트의 움직임대로 시작지점부터 bfs해서 도착지점에 최초도달하는 레벨이 최단 거리이다.

(BFS는 해당 순회하는 신장 트리에서의 level-order를 탐색하므로, 가중치가 따로 없는 경우 최단 거리이다.)

 

코드

C++

#include <bits/stdc++.h>
#define pii pair<int, int>

using namespace std;

vector<pii> knightMoves = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2},
                           {1, -2},  {1, 2},  {2, -1},  {2, 1}};

void solve() {
  int l;
  pii s, e;

  cin >> l >> s.first >> s.second >> e.first >> e.second;
  vector<vector<bool>> visited(l, vector<bool>(l, false));
  queue<pii> q;
  q.push(s);
  visited[s.first][s.second] = true;

  int depth = 0;
  while (!q.empty()) {
    int qsize = q.size();
    for (int i = 0; i < qsize; ++i) {

      auto [x, y] = q.front();
      q.pop();
      if (x == e.first && y == e.second) {
        cout << depth << "\n";
        return;
      }

      for (const auto &[dx, dy] : knightMoves) {
        int nx = x + dx;
        int ny = y + dy;

        if (nx < 0 || nx >= l || ny < 0 || ny >= l || visited[nx][ny])
          continue;
        visited[nx][ny] = true;
        q.push({nx, ny});
      }
    }
    depth++;
  }
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int t;
  cin >> t;
  while (t--)
    solve();
  return 0;
}

 

Go

package main

import (
	"bufio"
	"fmt"
	"os"
)

var reader *bufio.Reader
var writer *bufio.Writer
var knightMoves = [][]int32{
	{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2},
	{1, -2}, {1, 2}, {2, -1}, {2, 1},
}

type Pair struct {
	First  int32
	Second int32
}

type Queue struct {
	data []Pair
}

func (q *Queue) Empty() bool {
	return len(q.data) == 0
}

func (q *Queue) Push(p Pair) {
	q.data = append(q.data, p)
}

func (q *Queue) Pop() (Pair, bool) {
	if q.Empty() {
		return Pair{}, false
	}
	front := q.data[0]
	q.data = q.data[1:]
	return front, true
}

func solve() {
	var l, sr, sc, er, ec int32
	fmt.Fscan(reader, &l)
	fmt.Fscan(reader, &sr, &sc)
	fmt.Fscan(reader, &er, &ec)

	visited := make([][]bool, l)
	for i := int32(0); i < l; i++ {
		visited[i] = make([]bool, l)
	}

	q := Queue{}
	q.Push(Pair{sr, sc})
	visited[sr][sc] = true
	depth := int32(0)

	for !q.Empty() {
		qsize := len(q.data)
		for i := 0; i < qsize; i++ {
			p, _ := q.Pop()
			x := p.First
			y := p.Second

			if x == er && y == ec {
				fmt.Fprintln(writer, depth)
				return
			}

			for _, mov := range knightMoves {
				nx := x + mov[0]
				ny := y + mov[1]

				if nx < 0 || ny < 0 || nx >= l || ny >= l || visited[nx][ny] {
					continue
				}

				visited[nx][ny] = true
				q.Push(Pair{nx, ny})
			}
		}
		depth++
	}
}

func main() {
	reader = bufio.NewReader(os.Stdin)
	writer = bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var t int32
	fmt.Fscan(reader, &t)

	for t > 0 {
		solve()
		t--
	}
}