백준 14940번, 쉬운 최단거리

백준 14940번 c++ 문제풀이

문제:

백준 14940

풀이:

1. n은 세로, m은 가로길이로 이중벡터에 땅에 대한 정보를 저장한다.
2. 각 위치에서 목표지점까지의 거리 = 목표지점에서 각 위치까지의 거리
3. 목표지점부터 (x+1,y), (x-1,y), (x,y+1), (x, y-1)방향을 연결되어 있는 노드로 본다.
4. 위의 방향을 기준으로 너비우선탐색을 실행한다.(큐에 넣는 방식으로 진행)
5. 목표지점의 벡터값을 0으로 바꾼다. 너비우선탐색을 진행하여 다음 땅으로 이동하게 되면,
   이전 벡터에 저장된 값에 +1을 해서 벡터에 다시 저장한다.
6. 다시 저장된 벡터를 출력한다.

코드:

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

void bfs(vector<vector<int>> v, int x, int y, int m, int n){
    queue<pair<int, int>> q;
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    q.push({x, y});

    visited[y][x] = true;
    v[y][x] = 0;
    while(!q.empty()){
        int x1, y1; //현재 좌표
        x1 = q.front().first;
        y1 = q.front().second;
    
        q.pop();
        if(y1-1 >= 0){
            if(v[y1-1][x1]==1){
                if(visited[y1-1][x1] == false){
                    q.push({x1, y1-1});
                    visited[y1-1][x1] = true;
                    v[y1-1][x1] = v[y1][x1]+1;
                }
            }
        }
        if(x1-1 >= 0){
            if(v[y1][x1-1] == 1){
                if(visited[y1][x1-1] == false){
                    q.push({x1-1, y1});
                    visited[y1][x1-1] = true;
                    v[y1][x1-1] = v[y1][x1]+1;
                }
            }
        }
        if(x1+1 < m){
            if(v[y1][x1+1] == 1){
                if(visited[y1][x1+1] == false){
                    q.push({x1+1, y1});
                    visited[y1][x1+1] = true;
                    v[y1][x1+1] = v[y1][x1]+1;
                }
            }
        }
        if(y1+1 < n){
            if(v[y1+1][x1] == 1){
                if(visited[y1+1][x1] == false){
                    q.push({x1, y1+1});
                    visited[y1+1][x1] = true;
                    v[y1+1][x1] = v[y1][x1]+1;
                }
            } 
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(visited[i][j] == false && v[i][j] == 1){
                cout << -1 << " ";
            }else{
                cout << v[i][j] <<" ";
            }
        }
        cout << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;// 세로, 가로
    int x, y;//시작 좌표
    vector<vector<int>> v;

    cin >> n >> m;

    for(int i=0;i<n;i++){
        vector<int> v1;
        for(int j=0;j<m;j++){
            int input;
            cin >> input;
            v1.push_back(input);
            if(input == 2){
                y=i;
                x=j;
            }
        }
        v.push_back(v1);
    } 

    bfs(v, x, y, m, n);

    return 0;
}

감사합니다.