백준 [7562] "나이트의 이동"

쉬운 BFS문제였지만 실수로 오답이 나왔다. 다음에는 이번과 같은 실수를 하지 않기 위해 강조해서 기록하고자 한다.

1. 방문 선언은 재귀 하기전에 선언한다.

36줄 코드를 보면 현재 조건에 참이면 다음 Deque에 넣어 BFS를 실행하는 것을 확인 할 수있다. 여기서 조건중 현재 방문기록이 있는지 확인하는 부분이있는데 만약 현재 방문하지 않았다는 것의 조건(Visit[nx][ny] == false)을 확인 후 해당 26줄에서 바꾸는 것을 확인 할 수 있는데 이것은 위 8번의 좌표 찾기를 모두 실행하는 참사를 일어나게 했다.

그래서 수정 후 코드를 확인하면 조건을 확인 후 해당 방문기록을 업데이트 하여 불필요한 접근을 바로 차단해야 한다. 이렇게 하지 않으면 메모리 초과가 발생한다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

#define endl "\n"

using namespace std;
int t;
int a, b, c, d, e;
int chess[300][300];

int dx[8] = { 2, 1, -1,-2, -2, -1,  1, 2 };
int dy[8] = { 1, 2, 2 , 1, -1, -2, -2, -1 };
bool visit[300][300];

void bfs(int size, int sx, int sy, int gx, int gy) {

    deque<pair<int,pair<int, int>>> q;
    q.push_back({ 0,{sx,sy} });
    visit[sx][sy] = true;
    while (!q.empty()) {
        int x = q.front().second.first;
        int y = q.front().second.second;
        int cost = q.front().first;
        q.pop_front();
        if (x == gx && y == gy) {
            cout << cost << endl;
            return;
        }
        
        for (int i = 0; i < 8; i++) {
            int nx = dx[i] + x;
            int ny = dy[i] + y;
            if (nx >= 0 && nx < size && ny >= 0 && ny < size && visit[nx][ny] == false) {
                visit[nx][ny] = true;
                q.push_back({ cost + 1,{nx,ny} });
            }
        }
    }
}

int main() {
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

    cin >> t;

    for (int i = 0; i < t; i++) {
        memset(chess, 0, sizeof(chess));
        memset(visit, false, sizeof(visit));
        cin >> a;
        cin >> b;
        cin >> c;
        cin >> d;
        cin >> e;
        bfs(a,b,c,d,e);
    }

    return 0;

}