반응형
<문제> 백준 7562번
https://www.acmicpc.net/problem/7562
<풀이>
bfs를 이용하여 풀면 된다.
한 지점에서 다음 지점까지 가는 방법이 총 8개가 존재한다. 따라서 이는 8개의 인접 노드와 연결되어있는 그래프로 볼 수 있다.
lev값을 선언해준 다음 각 층의 깊이를 저장해주고, 원하는 목표가 탐색되면 바로 lev값을 출력해주면 된다.
<구현>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
#include<bits/stdc++.h>
#define fio() \
ios_base::sync_with_stdio(0); \
cin.tie(0)
using namespace std;
typedef tuple<ll, ll, ll> tpl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef tuple<int, int, int> tpi;
typedef tuple<double, int, int> dii;
const int cx[] = {1, 2, -1, -2, -1, -2, 1, 2};
const int cy[] = {2, 1, 2, 1, -2, -1, -2, -1};
int bfs(int sx, int sy, int l, int ex, int ey){
queue<pii> q;
q.push({sx, sy});
bool visited[303][303] = {};
visited[sx][sy] = true;
int lev = 0;
while(!q.empty()){
int qSize = q.size();
for(int i = 0; i < qSize; i++){
int x = q.front().first;
int y = q.front().second;
q.pop();
if(x == ex && y == ey) return lev;
for(int i = 0; i < 8; i++){
int nx = x + cx[i];
int ny = y + cy[i];
if(0 <= nx && nx < l && 0 <= ny && ny < l && !visited[nx][ny]){
q.push({nx, ny});
visited[nx][ny] = true;
}
}
}
lev++;
}
return -1;
}
int main(){
int T; scanf("%d", &T);
while(T--){
int l; scanf("%d", &l);
int sx, sy; scanf("%d %d", &sx, &sy);
int ex, ey; scanf("%d %d", &ex, &ey);
printf("%d\n", bfs(sx, sy, l, ex, ey));
}
}
|
cs |
'ps연습장' 카테고리의 다른 글
백준 2294번 : 동전 2 (C/C++) (0) | 2023.09.16 |
---|---|
백준 13305번 : 주유소 풀이 (C/C++) (0) | 2023.09.15 |
백준 15649번 N과 M (1) 풀이 (C/C++) (0) | 2023.09.15 |
백준 28297번 : 차량 모듈 제작(C/C++) (0) | 2023.07.02 |
백준 28257번 : 알록달록 초콜릿 만들기(C/C++) (0) | 2023.06.30 |