백준 7562. 나이트의 이동

www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

간단한 bfs 문제라 처음에 진짜 금방 풀었는데 실수 하나 때문에 그거 찾느라 애를 먹었다..

문제는 그냥 토마토 문제처럼 bfs 로 최단거리를 찾으면 되는데 다른 점은 체스말의 이동가능한 방향이 총 8방향 이라는 점만 다르다.

 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
#define MAX 301

int mark[MAX][MAX] = {0};
int I;
int idx = 1;

int dr[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dc[8] = {1, 2, 2, 1, -1, -2, -2, -1};


void init() {
    fill(&mark[0][0], &mark[MAX-1][MAX-1], 0);
    idx = 1;
}

void bfs(int r, int c, int dest_r, int dest_c) {
    queue<pair<int,int>> q;
    q.push({r,c});
    mark[r][c] = idx;

    while(!q.empty()) {
        int nr = q.front().first;
        int nc = q.front().second;
        q.pop();
        if(mark[nr][nc] > idx) idx++;

        if(nr == dest_r && nc == dest_c) {
            cout << mark[nr][nc]-1 << '\n';
            return;
        }

        for(int i = 0; i < 8; i++) {
            int nnr = nr + dr[i];
            int nnc = nc + dc[i];

            /* 범위 주의!! */
            if(nnr < 0 || nnr >= I || nnc < 0 || nnc >= I) continue;

            if(mark[nnr][nnc] == 0) {
                q.push({nnr, nnc});
                mark[nnr][nnc] = idx + 1;
            }

        }
    }
}


int main() {
    int T;
    cin >> T;

    while(T--) {
        int r, c;
        int dest_r, dest_c;

        cin >> I;
        cin >> r >> c;
        cin >> dest_r >> dest_c;

        bfs(r,c, dest_r, dest_c);

        init();
    }







}

 

/* 범위 주의!! */
if(nnr < 0 || nnr >= I || nnc < 0 || nnc >= I) continue;

 

이 부분에 범위를 nnr > I 이런식으로 해서 틀렸었다.

 

 

---

bfs 함수안에서 

if(nr == dest_r && nc == dest_c) {
            cout << mark[nr][nc]-1 << '\n';
            return;
        }

이런식으로 답을 찾은후 리턴하지 않고 그냥 큐가 빌때까지 반복하고 함수를 빠져나오면 실행시간이 48ms가 나오고

위처럼 답을 찾은후 바로 빠져나오면 실행시간이 28ms가 나왔다. 

이런문제를 풀때 지금까지 안빠져나오고 그냥 큐가 빌때까지 루프를 돌았던것같은데 이제부턴 잘생각해서 조건이 맞으면 탈출하도록 해야겠다.