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

문제

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

입력

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

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

출력

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

 

이 문제는 의외로 간단하다.

하지만 주의 해야할점은 나이트의 이동 경로를 파악하는게 가장 우선이듯 싶다.

현재 나는 좌표에 덜 적응?된 상태이므로 그림을 그려서 해결했다.

 

대충 초록색 칸으로 가는 문제다. 이것을 토대로 좌표를 구해보면

(1,2),(2,1),(-1,2),(-2,1),(-2,-1),(-2,-1),(-2,1),(-1,2)이걸 x좌표와 y좌표로 구분해서 작성하면 된다.

물론 1과 2로 반복이 되기때문에 어떻게 하면 더 간단하게 할 수도 있지만 귀찮기도 하고, 굳이라는 생각이 들어 하지 않을거다. 하지 못하기도 한다. 시도 조차 안했으니까

 

x좌표와 y좌표를 나누는 기준은 없다. 어떤것을 먼저 시작하든 상관없다. 하지만 x좌표에서 시작한 좌표와 y좌표와 시작한 값이 일치해야한다.

 

이것을 다하고 나면 90%는 끝났다. bfs를 돌리면서 값을 찾으면 된다.

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dx[8] = {-1,1,2,2,1,-1,-2,-2};
int dy[8] = {2,2,1,-1,-2,-2,-1,1};

void solution() {
   int l;
  int s1,s2;
  int e1,e2;

  bool visit[500][500];
  int go[500][500];
  
  cin >> l;

  for(int i = 0; i<l;i++) {
    for(int j = 0; j<l;j++) {
      visit[i][j] = false;
      go[i][j] = 0;
    }
  }
  cin >> s1 >> s2;

  cin >> e1 >> e2;

  queue<pair<int,int>> q;
  q.push({s1,s2});

  visit[s1][s2] = true;

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

    for(int i = 0;i<8;i++) {
      int nx = cur.X + dx[i];
      int ny = cur.Y + dy[i];

      if (ny < 0 || l <= ny || nx < 0 || l <= nx ) continue;

      if (visit[nx][ny]) continue;
      
      q.push({nx,ny});
      go[nx][ny] = go[cur.X][cur.Y] + 1;
      visit[nx][ny] = true;
    }
  }


  cout << go[e1][e2] << "\n";
}

int main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  int tc;
  cin >> tc;
  while (tc--) {
  solution();
  }
} 

초기화를 왜 memset이나 fill을 사용하지 않는 이유는 사용법을 모르기도 하고, 이게 편해서 이렇게 사용했다. 추후에 방법을 알게 되면 그때가서 생각해야지.

 

bfs하면서 주의해야할점은 for문안은 다음 이동경로이지 현재 경로가 아니다. 당연한 말처럼 들릴 수 있겠지만 나는 이걸 자꾸 잊여서 못 푼문제가 생각의뢰로 많다.ㅜㅜ

 

#include <bits/stdc++.h>

using namespace std;

int L;
bool visit[301][301] = {};

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

int main()
{
	int T;
	scanf("%d", &T);

	while(T--)
	{
		scanf("%d", &L);
		memset(visit, 0, sizeof(visit));		
		int sy, sx;
		int ey, ex;
		scanf("%d%d", &sy, &sx);
		scanf("%d%d", &ey, &ex);

		queue<pair<int, int>> bfs;
		bfs.push({sy, sx});
		visit[sy][sx] = true;

		int ans = 0;

		while(!bfs.empty())
		{
			int size = bfs.size();
			while(size--)
			{
				int y = bfs.front().first;
				int x = bfs.front().second;
				bfs.pop();

				if(y == ey && x == ex)
				{
					printf("%d\n", ans);
					ans = -1;
					break;
				}

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

					if(ny < 0 || ny >= L || nx < 0 || nx >= L || visit[ny][nx])
						continue;

					visit[ny][nx] = true;
					bfs.push({ny, nx});
				}
			}
			if(ans == -1)
				break;
			ans++;
		}

		if(ans != -1)
			puts("0");
	}

	return 0;
}