반응형
7562번: 나이트의 이동
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수
www.acmicpc.net

풀이 )
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 : 시간초과
반응형
'문제풀이 > 백준' 카테고리의 다른 글
[C++][JAVA] 백준 - 1012 : 유기농 배추 (0) | 2020.11.20 |
---|---|
[C++] 백준 - 2075 : N번째 큰 수 (0) | 2020.11.20 |
[C++] 백준 - 3085 : 사탕 게임 (0) | 2020.11.06 |
[C++] 백준 - 2231 : 분해합 (0) | 2020.11.06 |
[C++] 백준 - 1697 : 숨바꼭질 (0) | 2020.05.01 |