[BOJ/14940번쉬운최단거리] c++ / BFS

문제

각 지점에 대한 목표지점까지의 최단거리를 구하는 문제

 

생각

목표지점에 인접한 상하좌우는 동일한 거리 값을 가짐

 

문제풀이

1.목표지점의 좌표가 나오면 저장 + 0일 경우 vis에 -2 / 1일 경우 vis에 -1 저장 ( 땅인데 목표지점 까지 가지 못했을 경우를 생각해서 )

2.BFS 탐색

3.기준칸의 상하좌우 탐색

3-1.방문표시 없고, 땅이라면 큐에 푸쉬 + vis에 기준 칸 값 + 1

4.vis가 -2인 경우(땅이 아닌 경우) 0 출력

4.아닌 경우, vis 출력 ( 땅인데 목표지점까지 가지 못했을 경우는 -1이 출력됨: 1번 과정 )

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define X first
#define Y second
int dx[4] = {0, 1, -1, 0};
int dy[4] = {1, 0, 0, -1};
int board[1001][1001];
int vis[1001][1001];
int x, y, N, M;
void BFS() {
    queue<pair<int, int>> Q;
    vis[x][y] = 0; // 목표지점 
    Q.push({x, y});
    while(!Q.empty()) {
        pair<int, int> cur = Q.front(); Q.pop();

        for ( int dir = 0; dir < 4; dir++ ) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];

            if ( nx < 0 || nx >= N || ny < 0 || ny >= M ) continue;
            if ( !board[nx][ny] || vis[nx][ny] > -1 ) continue;
            
            vis[nx][ny] = vis[cur.X][cur.Y] + 1;
            Q.push({nx, ny});
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for ( int i = 0; i < N; i++ ) 
        for ( int j = 0; j < M; j++ ) {
            cin >> board[i][j];
            if ( board[i][j] == 1 )
                vis[i][j] = -1;
            else if ( board[i][j] == 0 )
                vis[i][j] = -2;
            if ( board[i][j] == 2 ) {
                x = i;
                y = j;
            }
        }
    
    BFS();

    for ( int i = 0; i < N; i++ ) {
        for ( int j = 0; j < M; j++ ) {
            if ( vis[i][j] == -2 )
                cout << 0 << " ";
            else
                cout << vis[i][j] << " ";
        }
        cout << "\n";
    }

}