개요

백준 7562: 나이트의 이동

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

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

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

접근 방식

1. 백준 2178(미로탐색 ) 문제와 똑같다.
   차이점은 미로탐색은 상하좌우에 갈 수 있는 칸이 정해져 있지만,
   이 문제는 나이트의 움직임대로 가야하고, 모든 칸을 경유해서 도착지에 갈 수 있다.

2. BFS방식을 사용해 각 레벨에서 큐의 front값이 목표지점인지 체크하여
   목표지점이면 레벨 출력, 목표지점이 아니라면 계속 반복하는 방법이다.

3. 나이트의 움직임은 현재 좌표가 0,0일때
   (2,-1)(2,1)(-2,-1)(-2,1)(1,2)(1,-2)(-1,-2)(-1,2)
   이렇게 총 8군데 가게되므로, 미리 배열에 지정하고 반복문을 이용해 8부분을 한번에 처리가능하다

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

for (int i = 0; i < 8; i++) {
	int NextX = cur.first + dx[i];
	int NextY = cur.second + dy[i];
    }

코드

#include<iostream>
#include<queue>

using namespace std;
int testCases = 0, chessFieldLen = 0;
int dx[8] = {1,-1,2,2,-2,-2,1,-1};
int dy[8] = {2,2,1,-1,1,-1,-2,-2};
int visited[301][301];

void BFS(pair<int, int>sPoint, pair<int, int>ePoint) {
	//시작좌표와 끝좌표 같다면 0출력
	if (sPoint == ePoint) {
		cout << 0 << '\n';
		return;
	}

	//bfs에 쓰일 큐 선언
	queue<pair<int,int>> q;
	//시작 포인트는 방문했으므로 방문 체크
	visited[sPoint.first][sPoint.second] = 1;
	//큐에 시작 포인트 집어넣기
	q.push(sPoint);
	//시작 레벨은 1로 설정
	int level = 1;
	while (!q.empty()) {
		//큐의 사이즈는 가변적이므로 미리 변수에 할당
		int qSize = q.size();
		//큐사이즈만큼 반복하면 레벨 하나 끝난것
		for (int i = 0; i < qSize; i++) {
			//큐의 front값 저장
			pair<int, int> cur = q.front();
			//큐 pop
			q.pop();
			//현재좌표가 0,0일때 (2,-1)(2,1)(-2,-1)(-2,1)(1,2)(1,-2)(-1,-2)(-1,2)총 8군데 갈 수 있으므로 8곳 다 체크
			for (int i = 0; i < 8; i++) {
				int NextX = cur.first + dx[i];
				int NextY = cur.second + dy[i];
				//종결 좌표값과 같아지면 해당 레벨 출력
				if (NextX == ePoint.first && NextY == ePoint.second) {
					cout << level << '\n';
					return;
				}
				// 특정 위치로 가야하는 조건이 없으므로 범위 내에 있기만 하면됨
				if (NextX >= 0 && NextY >= 0 && NextX < chessFieldLen && NextY < chessFieldLen) {
					//방문한적 없다면 
					if (!visited[NextX][NextY]) {
						//방문 체크한 후
						visited[NextX][NextY] = 1;
						//큐에 집어넣음
						q.push({ NextX,NextY });
					}
				}

			}
		}
		level++;
	}
}


void input() {
	pair<int, int> startPoint, endPoint;
	int tmp1=0, tmp2=0;
	//테스트케이스 수 받아옴
	cin >> testCases;
	for (int i = 0; i < testCases; i++) {
		// 체스판 길이
		cin >> chessFieldLen;
		//시작좌표
		cin >> tmp1 >> tmp2;
		startPoint = { tmp1,tmp2 };
		//타겟좌표
		cin >> tmp1 >> tmp2;
		endPoint = { tmp1,tmp2 };
		//방문 배열 false로 채우기
		fill(&visited[0][0], &visited[chessFieldLen][chessFieldLen], false);
		BFS(startPoint, endPoint);
	}
}

int main() {
	input();
}

문풀후생

실수한 부분은
visited배열 각 반복문마다 초기화하는 것, 시작좌표와 종결좌표 같을때 처리, dx배열에서 음양 표기 잘못한 부분이다..