백준 14940번 쉬운 최단 거리 - C++ 풀이

---

 

1. BFS를 사용하여 두 지점 사이의 거리를 구할 수 있다.
2. BFS의 출발 노드를 목표지점으로 설정하여 모든 칸까지의 거리를 한번에 계산한다.

 

1. BFS를 사용하여 두 지점 사이의 거리를 구할 수 있다.

각 칸을 노드로 생각하고 갈 수 있는 땅끼리는 연결하여 그래프를 만든다. 이제 BFS를 사용하면 두 지점 사이의 거리를 구할 수 있다.

 

2. BFS를 사용하여 목표지점에서 모든 칸까지의 거리를 한번에 계산한다.

각 칸에서 출발하여 목표지점까지 도달하는 BFS를 수행한다면, 총 n^2개의 칸에 대해 O(n^2)의 시간복잡도가 소요되므로 총 시간복잡도는 O(n^4)가 되어 시간초과를 받을 수 있다. 거꾸로 목표지점에서 출발하여 모든 칸을 방문하는 BFS를 진행하면 한번에 계산이 가능하다. 각 노드를 방문할 때마다 이전 방문 노드까지의 거리 + 1로 갱신해주면 된다.

 

---

#include <iostream>
#include <queue>

using namespace std;

typedef pair<int, int> pii;

const int MAX_N = 1000;
const int POSSIBLE = 1, GOAL = 2;

int n, m;
int goal_r, goal_c;
int board[MAX_N][MAX_N];
int dist[MAX_N][MAX_N];
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};

void calcDist() {
    queue<pii> q;
    
    // 1. BFS로 목표지점과의 거리 계산
    q.push({goal_r, goal_c});
    
    while (!q.empty()) {
        pii curr = q.front(); q.pop();
        int r = curr.first;
        int c = curr.second;
        
        for (int i=0; i<4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            
            if (board[nr][nc] == POSSIBLE && dist[nr][nc] == 0) {
                dist[nr][nc] = dist[r][c] + 1;
                q.push({nr, nc});
            }
        }
    }
    
    // 2. 도달할 수 없는 위치 처리
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            if (board[i][j] == POSSIBLE && dist[i][j] == 0) {
                dist[i][j] = -1;
            }
        }
    }
}

int main()
{
    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] == GOAL) {
                goal_r = i;
                goal_c = j;
            }
        }
    }
    
    calcDist();
    
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            cout << dist[i][j] << " ";
        }
        cout << "\n";
    }
}