[BOJ] #7562 나이트의 이동

시간 제한	메모리 제한	정답 비율
1 초	256 MB	43.859%

 

7562번: 나이트의 이동

 

문제

체스판 위의 나이트를 몇 번 움직여 현재 위치에서 목적지까지 갈 수 있는지 횟 수를 출력하는 문제이다.

나이트의 이동

나이트의 이동을 인덱스로 표현하여 dx, dy 라는 배열에 저장해두었고 반복문을 돌면서 해당 인덱스에서 몇 번째 이동이었는지를 chk[][]에 저장하고, 해당 인덱스가 목적지와 같다면 함수를 끝내고 답을 출력했다.

 

시행착오

계속 맞는데 왜 틀릴까 했더니 dx 를 계속 int dx[] = { -2,-1,1,2,2,1,-1,-1 } 로 쓰고 있었다. 제대로 고치고 성공. 너무나도 허무했다. 미리미리 실수하지 않게 꼼꼼하게 확인하자.

메모리	시간
2352  KB	20 ms

#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
typedef pair<int, int> p;
int dx[] = { -2,-1,1,2,2,1,-1,-2 }, dy[] = { 1,2,2,1,-1,-2,-2,-1 };
int t, n, chk[305][305], ans;
p start, destination;
void bfs(int x, int y) {
    if (x == destination.first && y == destination.second) {
        ans = 0; 
        return;
    }
    queue <p> q;
    q.push({ x, y });
    chk[x][y] = 0;
    
    while (!q.empty()) {
        int r = q.front().first, c = q.front().second;
        q.pop();
        for (int i = 0; i < 8; i++) {
            int nr = r + dx[i], nc = c + dy[i];
 
            if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
            if (chk[nr][nc] > 0) continue;
            chk[nr][nc] = chk[r][c] + 1;
            if (nr == destination.first && nc == destination.second) {
                ans = chk[nr][nc]; return;
            }
            q.push({ nr, nc });
        }
    }
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        scanf("%d %d %d %d", &start.first, &start.second, &destination.first, &destination.second);
        memset(chk, -1, sizeof(chk));
        ans = 0;
 
        bfs(start.first, start.second);
 
        printf("%d\n", ans);        
    }
    return 0;
}

 

참고 사항

for 문을 아래와 같이 작성하게 되면 코드는 조금 줄어들지 몰라도 시간은 4 ms 만큼 증가한다!

for (int i = 0; i < 8; i++) {
    int nr = r + dx[i], nc = c + dy[i];
 
    if (nr >= 0 && nr < n && nc >= 0 && nc < n && chk[nr][nc] < 0) {
        chk[nr][nc] = chk[r][c] + 1;
        if (nr == destination.first && nc == destination.second) {
            ans = chk[nr][nc]; return;
        }
        q.push({ nr, nc });
    }
}