[C++] 백준 14940번: 쉬운 최단거리 (BFS)

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

---

문제 이해하기

각 지점에서 목표지점까지의 최단거리를 구하여라.

---

시간복잡도 어림하기

BFS 알고리즘

 가중치가 같은 최단거리 문제이므로 BFS를 사용하여 해결할 수 있습니다. 탐색 범위인 n x m은 최대 1,000,000 이므로 제한 시간내에 문제를 해결하기 충분한 수치입니다.

---

알고리즘 설계하기

 이번 문제는 특정 지점에서 목표 지점까지의 최단거리가 아닌, 모든 지점에서 목표 지점까지의 최단거리를 구하는 문제입니다. 이를 반대로 이야기하면 목표 지점에서 이동 가능한 모든 지점까지의 최단거리를 구하는 것과 같습니다. 따라서 BFS의 시작 위치를 목표지점으로 설정합니다.

 

 BFS 알고리즘은 일반적으로 다음과 같이 구현합니다.

1. queue에 시작 지점 push 및 시작 지점 방문처리
2. queue가 빌 때까지 아래 동작 반복
 2-1. queue의 가장 앞 원소 꺼내기
 2-2. 꺼낸 위치를 기반으로 이동 가능한 다음 위치 탐색
 2-3. 방문하지 않았고, 이동가능한 위치라면 queue에 push 및 방문처리

 

 또한, 이번 문제는 최단거리도 구해야 하므로 방문처리를 할때 현재 위치에서의 방문 처리값 + 1로 다음 위치를 방문처리하여 최단거리를 계산합니다.

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

#include<iostream>
#include<queue>
#include<tuple>
using namespace std;

int n, m, a[1004][1004], visited[1004][1004], sy, sx;
queue<pair<int, int>> q;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, -1, 0, 1};
int main(){
	/*입출력 성능 향상*/
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    int num;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> num; a[i][j] = num;
            if(num == 2){ sy = i; sx = j;}
        }
    }

	/*BFS 시작*/
    visited[sy][sx] = 1;
    q.push({sy, sx});
    int y, x;
    while(!q.empty()){
        tie(y, x) = q.front(); q.pop();
        for(int i = 0; i < 4; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
            if(visited[ny][nx] || a[ny][nx] == 0) continue;
            visited[ny][nx] = visited[y][x] + 1; //최단 거리 계산
            q.push({ny, nx});
        }
    }
    
    /*결과 출력*/
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(visited[i][j] > 0) cout << visited[i][j] - 1 << " ";
            else if(a[i][j] > 0) cout << -1 << " ";
            else cout << 0 << " ";
        }
        cout << '\n';
    }
    return 0;
}

 입력으로 들어온 값이 2일 때, 그 위치를 시작 위치로 지정합니다. 이후 BFS로 탐색하면서 최단거리를 갱신합니다.

 

 탐색이 끝나면 최단거리를 출력합니다. 이때, 최단거리를 방문처리 배열 값에 1을 뺀 값으로 하는 이유는 시작 위치에서 방문처리를 할 때 0이 아닌 1로 초기화했기 때문입니다.

---