본문 바로가기

알고리즘/BFS 문제풀이

[B7562] - 나이트의 이동

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

나이트는 가로로 2칸 세로로 1칸 혹은 가로로 1칸 세로로 2칸씩 이동합니다

그에 따라 dx[], dy[]를 설정할 때 실수가 없으면 간단하게 풀 수 있는 BFS문제입니다


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
#include <iostream>
#include <queue>
using namespace std;
int dx[] = { 1,1,-1,-1,2,2,-2,-};
int dy[] = { 2,-2,2,-2,1,-1,1,-};
struct pos {
    int x;
    int y;
};
int main()
{
    int t;
    cin >> t;
    for (int zs = 1; zs <= t; zs++)
    {
        int n;
        cin >> n;
        int map[301][301= { 0, };
        pos a[2];
        queue<pos>q;
        for (int i = 0; i < 2; i++) {
            cin >> a[i].x >> a[i].y;
        }
        q.push({ a[0].x,a[0].y });
        map[a[0].x][a[0].y] = 1;
        while (!q.empty())
        {
            int kx = q.front().x;
            int ky = q.front().y;
            q.pop();
            for (int z = 0; z < 8; z++)
            {
                int nx = kx + dx[z];
                int ny = ky + dy[z];
                if (nx >= && nx < n&&ny >= && ny < n&&map[nx][ny] == 0)
                {
                    map[nx][ny] = map[kx][ky] + 1;
                    q.push({ nx,ny });
                }
            }
            if (map[a[1].x][a[1].y] != 0)
                break;
        }
        cout << map[a[1].x][a[1].y]-<< '\n';
    }
}
cs

'알고리즘 > BFS 문제풀이' 카테고리의 다른 글