백준 7562

문제분석

 

체스판 길이(size)
8 -> 8 * 8 
나이트의 최초 시작 지점(startPoint)
나이트가 이동하려고 하는 칸(endPoint)

--> endPoint까지 최소 몇번만에 이동할수 있는지?

0. 시작지점을 큐에 넣음 

1. 나이트가 이동할 수 있는 모든 방향을 미리 지정해둠 
어떻게 지정할 것인가? 
총 8가지 방향 
ex) 0,0 기준으로 생각해보기 (x : 행, y : 열) 
1. 왼쪽상단
대각선(열감소, 행감소) -> 상(행감소)
x -> -2, y -> -1 
대각선(열감소, 행감소) -> 좌(열감소)
x -> -1, y -> -2

2. 오른쪽상단
대각선(열증가, 행감소) -> 상(행감소)
x -> -2, y -> +1 
대각선(열증가, 행감소) -> 우(열증가)
x -> -1, y -> +2

3. 왼쪽하단
대각선(열감소, 행증가) -> 좌(열감소)
x -> +1, y -> -2 
대각선(열감소, 행증가) -> 하(행증가)
x -> +2, y -> -1   

4. 오른쪽하단
대각선(열증가, 행증가) -> 우(열증가)
x -> +1, y -> +2 
대각선(열증가, 행증가) -> 하(행증가)
x -> +2, y -> +1

총 8가지 방향을 배열형태로 만듬 
int dx[8] = {-2, -1, -2, -1, 1, 2, 1, 2}
int dy[8] = {-1, -2, 1, 2, -2, -1, 2, 1}

2. 8가지 방향을 다 도는 도중에 해당 지점이 방문한 곳이 아니(dist가 0인 경우)라면 거리를 증가시킴
dist[x][y] = dist[cur.X][cur.Y] + 1;

 

코드

#include<iostream>
#include<queue>	
using namespace std;

int dist[301][301];

// 나이트가 이동할 수 있는 모든 방향
int dx[8] = { -2, -1, -2, -1, 1, 2, 1, 2 };
int dy[8] = { -1, -2, 1, 2, -2, -1, 2, 1 };

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	// 1.입력
	int T;
	cin >> T;

	for (int i = 0; i < T; i++) {
		int size;
		int startPtX, startPtY; 
		int	endPtX, endPtY;
		cin >> size;
		cin >> startPtX >> startPtY;
		cin >> endPtX >> endPtY;
		
		// 2.로직
		// dist 초기화 
		for (int a = 0; a < size; a++) {
			for (int b = 0; b < size; b++) {
				dist[a][b] = 0;
			}
		}

		queue<pair<int, int>> Q;
		dist[startPtX][startPtY] = 1;
		Q.push({ startPtX, startPtY });
		while (!Q.empty()) {
			pair<int, int> cur = Q.front();
			Q.pop();

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

				// 범위, 방문여부 체크
				if (nx < 0 || nx >= size || ny < 0 || ny >= size) continue;
				if (dist[nx][ny] > 0) continue;

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

		// 3.결과
		cout << dist[endPtX][endPtY] - 1 << "\n";
	}


	return 0;
}

코드 재풀이

#include<iostream>	
#include<queue>
using namespace std;

int vis[301][301];
// 좌상2, 좌하2, 우상2, 우하2
int dx[8] = { -1,-2,1,2,-2,-1,2,1 };
int dy[8] = { -2,-1,-2,-1,1,2,1,2 };
int I;


int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int t;
	cin >> t;
	queue<pair<int, int>> Q;
	while (t--) {
		cin >> I;
		int curNightPosX;
		int curNightPosY;
		int moveNightPosX;
		int moveNightPosY;
		cin >> curNightPosX >> curNightPosY;
		cin >> moveNightPosX >> moveNightPosY;

		// 초기화
		for (int i = 0; i < I; i++) {
			for (int j = 0; j < I; j++) {
				vis[i][j] = 0;
			}
		}

		vis[curNightPosX][curNightPosY] = 1;
		Q.push({ curNightPosX, curNightPosY });
		while (!Q.empty()) {
			pair<int, int> cur = Q.front(); Q.pop();

			if (cur.first == moveNightPosX && cur.second == moveNightPosY) {
				cout << vis[moveNightPosX][moveNightPosY] - 1 << '\n';
				break;
			}

			for (int dir = 0; dir < 8; dir++) {
				int nx = cur.first + dir[dx];
				int ny = cur.second + dir[dy];
				if (nx < 0 || nx >= I || ny < 0 || ny >= I) continue;
				if (vis[nx][ny] >= 1) continue;
				vis[nx][ny] = vis[cur.first][cur.second] + 1;
				Q.push({ nx, ny });
			}
		}
	}	
		
	return 0;
}

 

나이트가 이동하려는 칸에 위치할때 최소 이동 횟수를 출력하고 braek를 해서 while문을 탈출하지만, 

이때 Q에 값이 남아있는 경우 다음 테스트 케이스에서 영향을 끼치기 때문에 문제가 생길 수 있다.

Q에 있는 값이 빌때까지 작업을 계속하고 Q가 비게되면 while문을 빠져간 이후 최소 이동 횟수를 출력하는 방식으로 구현해야 함

 

#include<iostream>	
#include<queue>
using namespace std;

int vis[301][301];
// 좌상2, 좌하2, 우상2, 우하2
int dx[8] = { -1,-2,1,2,-2,-1,2,1 };
int dy[8] = { -2,-1,-2,-1,1,2,1,2 };
int I;


int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int t;
	cin >> t;
	queue<pair<int, int>> Q;
	while (t--) {
		cin >> I;
		int curNightPosX;
		int curNightPosY;
		int moveNightPosX;
		int moveNightPosY;
		cin >> curNightPosX >> curNightPosY;
		cin >> moveNightPosX >> moveNightPosY;

		// 초기화
		for (int i = 0; i < I; i++) {
			for (int j = 0; j < I; j++) {
				vis[i][j] = 0;
			}
		}

		vis[curNightPosX][curNightPosY] = 1;
		Q.push({ curNightPosX, curNightPosY });
		while (!Q.empty()) {
			pair<int, int> cur = Q.front(); Q.pop();			
			for (int dir = 0; dir < 8; dir++) {
				int nx = cur.first + dir[dx];
				int ny = cur.second + dir[dy];
				if (nx < 0 || nx >= I || ny < 0 || ny >= I) continue;
				if (vis[nx][ny] >= 1) continue;
				vis[nx][ny] = vis[cur.first][cur.second] + 1;
				Q.push({ nx, ny });
			}
		}
		
		cout << vis[moveNightPosX][moveNightPosY] - 1 << '\n';
	}	
		
	return 0;
}