[C++] 백준 - 7526 : 나이트의 이동

문제 링크

7562번: 나이트의 이동

 

풀이 )

  BFS를 이용한 문제이다.

  queue에 현재 나이트가 뛴 횟수와 나이트의 좌표를 pair로 묶어서 저장했다. 이 때, 각 좌표의 최댓값이 299이므로, 1000을 넘지 않아서 좌표를 간단하게 1000x+y 꼴로 나타냈다.

  매번 queue에 있는 front를 꺼내서 좌표를 확인한 후 좌표가 목표 좌표와 일치하는 경우 출력을 하고, 일치하지 않는 경우 나이트가 뛸 수 있는 8칸에 대해서 확인을 한다.

  나이트가 뛸 수 있는 8개의 방향 중 판에서 벗어나지 않고, 이전에 방문한 적 없는 칸에 방문하면서 이전과 같이 뛴 횟수를 한번 증가시키고, 이동한 좌표값을 1000x+y꼴로 바꾸어 pair로 묶은 다음에 다시 queue에 집어 넣는다.

#include <iostream>
#include <utility>
#include <queue>
#include <algorithm>

using namespace std;

int dir[8][2] = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
bool visited[300][300];

int main(void){
	int c;
	cin >> c;
	while(c--){
		int n, sx, sy, dx, dy;
		cin >> n;
		cin >> sx >> sy;
		cin >> dx >> dy;
		for(int i = 0; i < n; ++i)
			fill(visited[i], visited[i]+n, false);
		visited[sx][sy] = true;
		queue<pair<int, int>> q;
		q.push(make_pair(0, 1000*sx+sy));
		while(1){
			int move = q.front().first;
			int cur = q.front().second;
			int nx = cur/1000;
			int ny = cur%1000;
			if(nx == dx && ny == dy){
				cout << move << endl;
				break;
			}
			q.pop();
			for(int i = 0; i < 8; ++i){
				int xx = nx + dir[i][0];
				int yy = ny + dir[i][1];
				if(xx < 0 || xx >= n || yy < 0 || yy >= n)
					continue;
				if(!visited[xx][yy]){
					visited[xx][yy] = true;
					q.push(make_pair(move+1, xx*1000+yy));
				}
			}
		}
	}
	return 0;
}

 

주의점 )

- 방문 여부 초기화

- 판을 벗어나는 경우 예외처리 : 런타임 에러

- 방문한 칸 재방문 X : 시간초과