백준 7562: 나이트의 이동

나이트의 이동 성공다국어

한국어   

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

34754

17211

12869

48.584%

문제

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

입력

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

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

예제 입력 1 복사

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

 

예제 출력 1 복사

5
28
0

코드 

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int arr[301][301];
int visited[301][301];
int dy[8] = {-2,-1, 1,2, 2, 1, -1,-2};
int dx[8] = {1, 2, 2 ,1, -1,-2,-2,-1};

int T, n, y, x, py, px;
int answer;
queue<pair<int,int>> q;
void bfs(int y, int x) {
    q.push({ y,x });
    visited[y][x] = true;

    while (!q.empty()) {
        int yy = q.front().first;
        int xx = q.front().second;
        q.pop();
    
        if (yy == py && xx == px) {
            cout << arr[yy][xx] << '\n';
            break;
        }

        for (int i = 0; i < 8; i++) {
            int ny = yy + dy[i];
            int nx = xx + dx[i];

            if (ny > n - 1 || nx > n - 1 || ny < 0 || nx < 0)continue;

            if (visited[ny][nx] == false) {
                q.push({ ny,nx });
                visited[ny][nx] = true;
                arr[ny][nx] = arr[yy][xx] + 1;
            }
        }
    }

}

int main() {

    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> n;
        for (int a = 0; a < n; a++) {
            for (int b = 0; b < n; b++) {
                arr[a][b] = 0;
                visited[a][b] = 0;
                while (!q.empty()) q.pop();
            }
        }
        
        cin >> y >> x >> py >> px;
        bfs(y, x);
        
    }
    
    return 0;
}

bfs가 dfs에 비해서 상당히 빠르다는 느낌이 든다. 

처음에dfs로 짰는데 시간초과가 떴다.

 

그리고 문제 푸는거 너무 즐거운데, 오픽준비하느랴 자소서 쓰느랴 많이 못풀고 있다. 빅분기도 신청해놨는데 거의 공부도 못하고 it is tough life,,,