[BOJ] 14940 쉬운 최단거리

https://www.acmicpc.net/problem/14940

14940번: 쉬운 최단거리

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

bfs

 

---------------------------------------------------풀이----------------------------------------------------

 

출발 점에서 시작하며 이 때의 depth는 0으로 둔다.

<좌표, depth>를 큐에 저장하며, bfs 탐색을 한다.

큐의 front의 좌표에 해당하는 ans[][]에 depth를 저장하고 pop한다.

이 좌표의 상하좌우 네 방향을 탐색해 방문하지 않았다면 depth를 1 증가시켜 큐에 삽입한다.

큐가 empty가 되면 탐색을 종료한다.

 

출력할 때에는 map[][]이 1(갈 수 있는 곳)인데도 ans[][]가 0(방문하지 못한 곳)인 곳이면 -1을 출력하고,

이 케이스가 아니면 ans[][]에 거리가 저장되어 있으므로 이를 출력한다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>
#include <deque>

using namespace std;

int N, M;
int map[1001][1001] = {0, };
int ans[1001][1001] = {0, };
bool visited[1001][1001] = {false, };
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

void solution(pair<int,int> from){
    queue<pair<pair<int,int>,int> > q;
    // 좌표, depth
    pair<pair<int,int>,int> cur;
    cur.first = from; cur.second = 0;
    visited[cur.first.first][cur.first.second] = true;
    q.push(cur);
    while(!q.empty()){
        cur = q.front();
        q.pop();
        ans[cur.first.first][cur.first.second] = cur.second;
        for(int i = 0; i < 4; i++){
            int nx = cur.first.first + dx[i];
            int ny = cur.first.second + dy[i];
            if(nx < 0 || nx >= N || ny < 0 || ny >= M || map[nx][ny] == 0 || visited[nx][ny]){
                continue;
            }
            q.push(make_pair(make_pair(nx, ny), cur.second + 1));
            visited[nx][ny] = true;
        }
    }
}

// 모든 지점에 대해서 목표지점까지의 거리를 구해라. <=> 한 지점에서 모든 지점까지의 거리.
int main(void){
    FASTIO;
    cin >> N >> M;
    pair<int,int> from;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> map[i][j];
            if(map[i][j] == 2){
                from.first = i; from.second = j;
            }
        }
    }
    solution(from);
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            if(map[i][j] == 1 && ans[i][j] == 0){
                cout << -1 << " ";
            }
            else{
                cout << ans[i][j] << " ";
            }
        }
        cout << "\n";
    }

    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

한 점에서 모든 점까지의 거리를 보고, 다익스트라 알고리즘을 떠올렸으나 이 문제는 굳이...?라는 생각이 떠오르는 문제였다.

따라서 간단하게 bfs로 출발 점에서 시작해 <<x,y>, 거리>를 queue에 삽입하며 풀었다.