링크 : www.acmicpc.net/problem/7562
전형적인 BFS문제.
이 문제에서는 체스말의 위치값의 한 쌍 (x,y) 그리고 누적된 이동값 Num을 같이 저장하기 위해
1개의 요소와 2개의 요소를 pair형태로 Queue에 저장한 점이 인상깊었다
queue<pair<int,pair<int,int>>> q;
q.push(make_pair(0,make_pair(y,x)));
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int tc = 0, len = 0;
int ch[300][300];
int my[8] = {2,1,-1,-2,-2,-1,1,2}, mx[8] = {1,2,2,1,-1,-2,-2,-1};
void bfs(){
int y = 0 , x = 0;
int gy = 0, gx = 0;
cin >> len;
cin >> y >> x;
cin >> gy >> gx;
queue<pair<int, pair<int,int>>> q;
ch[y][x] = 0;
q.push(make_pair(0,make_pair(y,x)));
while(!q.empty()){
int ty = q.front().second.first;
int tx = q.front().second.second;
int num = q.front().first;
q.pop();
if(ty==gy&&tx==gx){
cout << num << "\n";
return;
}
for(int i=0; i<8; i++){
int ny = ty+my[i];
int nx = tx+mx[i];
int nn = num + 1;
if(ny>=0&&ny<len&&nx>=0&&nx<len){
if(ch[ny][nx]==0){
ch[ny][nx] = nn;
q.push(make_pair(nn,make_pair(ny,nx)));
}
}
}
}
}
int main(void){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> tc;
while(tc>0){
bfs();
memset(ch,0,sizeof(ch));
tc--;
}
return 0;
}
'🖥️ CS > Baekjoon Algorithms' 카테고리의 다른 글
#7569 토마토 (C++) 🍅 (0) | 2020.10.07 |
---|---|
#1541 잃어버린 괄호 (C++) (0) | 2020.10.06 |
#6603 로또 (C++) (0) | 2020.10.02 |
#2206 벽 부수고 이동하기 (C++) (0) | 2020.10.02 |
#2178 미로 탐색 (C++) (0) | 2020.10.01 |