[C++] 14940. 쉬운 최단거리

 

전형적인 bfs 문제로, 목표지점을 기준으로 각 좌표들의 최단거리를 구해주면 된다.

queue를 이용해 각 좌표들의 visited 처리와 함께 거리를 구해주었다.

 

 

#include <iostream>
#include <queue>
using namespace std;
int n, m, r, c;
int graph[1001][1001] = {0,};
int visited[1001][1001] = {0,};

//각 좌표의 상,하,좌,우를 탐색해준다.
int dir_n[4] = {-1,1,0,0};
int dir_m[4] = {0,0,-1,1};

//목표좌표를 기준으로 시작된다.
void bfs(int x, int y)
{
    queue<pair<int, int> >q;
    q.push(make_pair(x,y));
    visited[x][y] = 1;

    while(!q.empty())
    {
    	//좌표를 저장해주기 위해 pair형태로 저장해줌
        int nx = q.front().first;
        int ny = q.front().second;
        q.pop();

        for(int i=0; i<4; i++) {
            int dx = nx + dir_n[i];
            int dy = ny + dir_m[i];
			
            //이 좌표가 지도 안에 위치하면 탐색한다.
            if(dx >= 0 && dx < n && dy >= 0 && dy < m)
            {
            	//좌표가 방문을 하지 않았고 0이 아닐때 거리를 구한다.
                if(visited[dx][dy]==0 && graph[dx][dy]!=0)
                {
                    visited[dx][dy] = visited[nx][ny] + 1;
                    q.push(make_pair(dx, dy));
                }
            } 
        }
    }
}

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

    cin >> n >> m;


    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            cin >> graph[i][j];
            if(graph[i][j] == 2) {
                r = i; c = j;
            }
        }
    }

    bfs(r, c);

    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            if(graph[i][j] == 0) cout << 0 << " ";
            else cout << visited[i][j] - 1 << " ";
            // visited 처리를 해줘서 -1, 원래 갈 수 있는데 visited 가 0이라면 못가는 곳이므로 -1 출력됨
        }
        cout << "\n";
    }

    return 0;
}