๋ฌธ์
์ฒด์คํ ์์ ํ ๋์ดํธ๊ฐ ๋์ฌ์ ธ ์๋ค. ๋์ดํธ๊ฐ ํ ๋ฒ์ ์ด๋ํ ์ ์๋ ์นธ์ ์๋ ๊ทธ๋ฆผ์ ๋์์๋ค. ๋์ดํธ๊ฐ ์ด๋ํ๋ ค๊ณ ํ๋ ์นธ์ด ์ฃผ์ด์ง๋ค. ๋์ดํธ๋ ๋ช ๋ฒ ์์ง์ด๋ฉด ์ด ์นธ์ผ๋ก ์ด๋ํ ์ ์์๊น?
์ ๋ ฅ
์ ๋ ฅ์ ์ฒซ์งธ ์ค์๋ ํ ์คํธ ์ผ์ด์ค์ ๊ฐ์๊ฐ ์ฃผ์ด์ง๋ค.
๊ฐ ํ ์คํธ ์ผ์ด์ค๋ ์ธ ์ค๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. ์ฒซ์งธ ์ค์๋ ์ฒด์คํ์ ํ ๋ณ์ ๊ธธ์ด l(4 ≤ l ≤ 300)์ด ์ฃผ์ด์ง๋ค. ์ฒด์คํ์ ํฌ๊ธฐ๋ l × l์ด๋ค. ์ฒด์คํ์ ๊ฐ ์นธ์ ๋ ์์ ์ {0, ..., l-1} × {0, ..., l-1}๋ก ๋ํ๋ผ ์ ์๋ค. ๋์งธ ์ค๊ณผ ์ ์งธ ์ค์๋ ๋์ดํธ๊ฐ ํ์ฌ ์๋ ์นธ, ๋์ดํธ๊ฐ ์ด๋ํ๋ ค๊ณ ํ๋ ์นธ์ด ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
๊ฐ ํ ์คํธ ์ผ์ด์ค๋ง๋ค ๋์ดํธ๊ฐ ์ต์ ๋ช ๋ฒ๋ง์ ์ด๋ํ ์ ์๋์ง ์ถ๋ ฅํ๋ค.
๋ฐฑ์ค ์ค๋ฒ1.
bfs๋ก ํ๊ณ ๋ฐ๋ก ์์ ๋ฃ์ด๋ดค๋๋ฐ ใ ๋จผ๊ฐ ์ด์ํ๊ธธ๋ ๋ฌธ์ ๋ฅผ ๋ค์ ์ฝ์ด๋ดค๋๋....
์ด๋ ์นธ์ด ์/์๋/์์์ด ์๋๋ผ ๋ฌธ์ ์ ์๋ ๊ทธ๋ฆผ์ฒ๋ผ ์ด๋ํ๋๊ฑฐ์์;
๊ทธ๋์ ์์ ํ๊ณ ๋ฐ๋ก ์ ๋ต!
ํญ์ ๋ฌธ์ ๋ฅผ ๊ผผ๊ผผํ๊ฒ ์ฝ์...^^
์ด์ bfs ์๊ณ ๋ฆฌ์ฆ์ ์ฝ๋ค๊ณ ๋๊ปด์ง ์ ๋๋ก ์ต์ํด์ก๋ค. ์ญ์ ๋ง์ด ํ์ด๋ณด๋๊ฒ ๋ต์ธ๋ฏ.
๋์ ํ์ด
#include <iostream>
#include <queue>
using namespace std;
int answer = 0;
int dx[8] = {2, 1, 2, 1, -2, -1, -2, -1};
int dy[8] = {1, 2, -1, -2, 1, 2, -1, -2};
int l;
bool canGo(int visited[301][301], int x, int y){
if(x<0 || y<0 || x>=l || y>=l) return false;
if(visited[x][y]==1) return false;
return true;
}
void bfs(int x, int y, int lx, int ly){
int visited[301][301]={0};
int mat[301][301] = {0};
queue<pair<int, int>> q;
q.push({x, y});
while(!q.empty()){
pair<int, int> a = q.front();
q.pop();
for (int i = 0; i < 8; ++i){
int nx = a.first + dx[i];
int ny = a.second + dy[i];
if(nx==x && ny==y) continue;
if (canGo(visited, nx, ny)){
visited[nx][ny] = 1;
q.push({nx, ny});
mat[nx][ny] = mat[a.first][a.second] + 1;
}
if(nx==lx && ny==ly) break;
}
}
answer = mat[lx][ly];
}
int main(){
int t;
int x;
int y;
int lx;
int ly;
cin >> t;
for (int i = 0; i < t; ++i){
cin >> l >> x>>y >> lx>>ly;
bfs(x,y,lx,ly);
cout << answer << "\n";
answer = 0;
}
}
'๐ ์๊ณ ๋ฆฌ์ฆ > BOJ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[C++/BOJ] 9663 : N-Queen (์์ ํ์, Backtracking) (0) | 2023.03.06 |
---|---|
[C++/BOJ] 1158 : ์์ธํธ์ค ๋ฌธ์ (Queue) (0) | 2023.03.03 |
[C++/BOJ] 1309 : ๋๋ฌผ์ (DP) (0) | 2023.02.23 |
[C++/BOJ] 2225 : ํฉ๋ถํด (DP) (0) | 2023.02.23 |
[C++/BOJ] 1697 : ์จ๋ฐ๊ผญ์ง (BFS) (0) | 2023.02.23 |