문제 요약

크기 n×m의 체스판에서 특정 위치 (x,y)에 있는 말이 각 위치로 이동하는 최단 거리를 계산해야 한다.

입력 형식

입력은 n, m, x, y 네 정수로 구성된다.

출력 형식

n×m 행렬 형태로 각 지점 도달 최단 거리를 출력한다(도달 불가 시 -1).

입력 출력 예시

입력 #1 ``` 3 3 1 1

출력 #1 ```
0    3    2    
3    -1   1    
2    1    4    <br></br><br></br>문제 자체는 간단하지만, 최단 경로 계산 시 너비 우선 탐색(BFS)을 사용하는 것이 효율적이다<br></br>특이한 현상을 발견해 공유한다. 먼저 메모리 초과(MLE)와 시간 초과(TLE) 발생 코드를 확인하자:<br></br></strong>

#include<bits/stdc++.h>
using namespace std;
const int MAX=500;
int width, height, start_x, start_y, grid[MAX][MAX];     
int move_x[8]={-1,-2,-2,-1,1,2,2,1},move_y[8]={2,1,-1,-2,2,1,-1,-2};
struct Point{
    int x,y,step;
};
int visited[MAX][MAX];
void bfs()
{
    queue<Point>q;
    Point init;
    init.x=start_x,init.y=start_y,init.step=0;
    q.push(init);
    visited[start_x][start_y]=0;
    while(!q.empty()){
        Point current=q.front();
        q.pop();
        visited[current.x][current.y]=current.step;
        for(int i=0;i<8;i++){
            int nx=current.x+move_x[i],ny=current.y+move_y[i];
            if(nx>=1&&ny>=1&&nx<=width&&ny<=height&&visited[nx][ny]==-1){
                Point next;
                next.x=nx,next.y=ny,next.step=current.step+1;
                q.push(next);
            }
        }
    }
    return ;
}
int main()
{
    cin>>width>>height>>start_x>>start_y;
    memset(visited, -1, sizeof visited);
    bfs();
    for(int i=1;i<=width;i++){
        for(int j=1;j<=height;j++) cout<<visited[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}

정상 작동 코드:

#include<bits/stdc++.h>
using namespace std;
const int MAX=500;
int width, height, start_x, start_y, grid[MAX][MAX];     
int move_x[8]={-1,-2,-2,-1,1,2,2,1},move_y[8]={2,1,-1,-2,2,1,-1,-2};
struct Point{
    int x,y,step;
};
int visited[MAX][MAX];
void bfs()
{
    queue<Point>q;
    Point init;
    init.x=start_x,init.y=start_y,init.step=0;
    q.push(init);
    visited[start_x][start_y]=0;
    while(!q.empty()){
        Point current=q.front();
        q.pop();
        for(int i=0;i<8;i++){
            int nx=current.x+move_x[i],ny=current.y+move_y[i];
            if(nx>=1&&ny>=1&&nx<=width&&ny<=height&&visited[nx][ny]==-1){
                Point next;
                next.x=nx,ny=current.y+move_y[i],next.step=current.step+1;
                visited[nx][ny]=current.step+1;
                q.push(next);
            }
        }
    }
    return ;
}
int main()
{
    cin>>width>>height>>start_x>>start_y;
    memset(visited, -1, sizeof visited);
    bfs();
    for(int i=1;i<=width;i++){
        for(int j=1;j<=height;j++) cout<<visited[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}

여기서 중요한 점은, for 루프 내에서 방문 배열을 즉시 업데이트하지 않으면 왜 메모리/시간 초과가 발생하는가?

외부 루프에서 이미 방문 표시를 했지만, BFS 특성상 중복 처리가 발생할 수 있다.

방문 배열을 즉시 업데이트하지 않으면, 동일한 노드가 여러 번 큐에 추가되어 메모리 사용량이 급증하고 처리 시간이 증가한다