https://www.acmicpc.net/problem/7562
7562번: 나이트의 이동
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수
www.acmicpc.net
실버 1의 문제이다. 그냥 조금 복잡한 최소이동 문제이다. 이동할 수 있는 방향이 8가지여서 그거만 조금 조심해주고 reset만 잘해주면 어렵지 않은 문제이다.
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int n,cnt;
int fromx,fromy,tox,toy;
int dist[301][301];
int visited[301][301];
int dx[]={-2,-1,1,2,2,1,-1,-2};
int dy[]={1,2,2,1,-1,-2,-2,-1};
queue<pair<int,int>> q;
void reset(){
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
visited[i][j] = 0;
dist[i][j] = 0;
}
}
while(!q.empty()){
q.pop();
}
}
void bfs(int x,int y){
q.push(make_pair(x,y));
visited[x][y]=1;
while(!q.empty()){
x=q.front().first;
y=q.front().second;
q.pop();
for(int k=0;k<8;k++){
int nx=x+dx[k];
int ny=y+dy[k];
if(0<=nx && nx<n && 0<=ny && ny<n){
if(visited[nx][ny]==0){
q.push(make_pair(nx,ny));
visited[nx][ny]=1;
dist[nx][ny]=dist[x][y]+1;
if(nx==tox && ny==toy) return;
}
}
}
}
}
int main()
{
freopen("input.txt","r",stdin);
int t;
cin>>t;
while(t--){
cin>>n;
cin>>fromx>>fromy;
cin>>tox>>toy;
reset();
if(fromx==tox && fromy==toy){
cout<<"0"<<'\n';
}
else{
bfs(fromx,fromy);
cout<<dist[tox][toy]<<'\n';
}
}
}처음 이 문제를 풀었을때는 계속 틀렸다고 나와서 잠깐 포기했던 문제이다. 지금 다시 풀어보니 그때 뭘 잘못했는지 단번에 알아차렸다.
일단 그때는 map[301][301] 이라는 배열을 사용해서 bfs함수 안에 쓸데없이 map함수를 들먹였었다. 근데 잘 보면 나이트가 이동할 수 있는 체스판에 뭐 1이 써있는것도아니고 if( map[nx][ny] == 1 ~~~) 라는식의 조건문을 쓸 필요가 없었다. 그래서 당장 map배열을 없애버렸다.
두번째 문제, 그때는 bfs함수 내에서 if(nx==tox && ny==toy) return; 이 부분이 없었다. 그니까 한번 bfs를 시작하면 그냥 무지성으로 갈 수 있을때까지 다 탐색하는것이다. 이럴 필요가 전혀 없다. 우리가 원하는 tox,toy 까지 가면 그즉시 함수를 종료하고 dist배열에서 원하는 값을 출력하면 되기 때문에 이 줄을 적어주었다. 사실 이 부분때문에 예전에 계속 틀렸다고 나온것 같다.
다른 부분은 그냥 무난한 최소 어쩌구 저쩌구 찾기 이므로 bfs를 이용하고 dist배열을 잘 이용했다면 오케이였다.
