[C++/BOJ] 7562 : 나이트의 이동 (BFS)

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 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;
    }
}