본문 바로가기
ps연습장

백준 7562번 : 나이트의 이동 (C/C++)

by hwsyl 2023. 9. 16.
반응형

<문제> 백준 7562번

https://www.acmicpc.net/problem/7562

백준 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<intint> pii;
typedef pair<ll, ll> pll;
typedef pair<doubledouble> pdd;
typedef tuple<intintint> tpi;
 
 
 
typedef tuple<doubleintint> dii;
 
 
const int cx[] = {12-1-2-1-212};
const int cy[] = {2121-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