[C++] 백준 쉬운 최단거리

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

14940번: 쉬운 최단거리

풀이

시작 지점에서 모든 도달 가능한 지점까지의 최단거리를 구하는 문제입니다. 단, 지도상 0이 아니지만 도달 불가능한 지점에 대해서는 -1을 출력해야 합니다. 최단 거리 문제이므로 BFS 알고리즘을 사용해 해결할 수 있습니다.

 

시작 지점은 입력을 받는 당시 2인 지점을 찾아 미리 goal_row, goal_col 변수에 담아둡니다. 

이후, 방문 판단 변수 visited와 거리 저장 변수 dist를 사용해 BFS 알고리즘을 구현합니다. 이 때, Info 구조체를 사용해 다음 지점의 row, col, dist를 저장해주었습니다.

 

리뷰

오랜만에 백준을 풀었더니 freopen을 지우지 않아서 런타임 에러가 나는 부분을 한참 찾았다... 

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

using namespace std;

int drow[4] = {0, 1, 0, -1};
int dcol[4] = {1, 0, -1, 0};

struct Info 
{
    int r;
    int c;
    int dist;
    Info(int a, int b, int dist) {
        r = a;
        c = b;
        this->dist = dist;
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    // freopen("test.txt", "r", stdin);
    int row, col; 
    int goal_row, goal_col;
    int num;
    cin >> row >> col;
    vector<vector<int>> map(1001, vector<int> (1001, 0));
    vector<vector<int>> visited(1001, vector<int> (1001, 0));
    vector<vector<int>> dist(1001, vector<int> (1001, 0));

    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            cin >> num; 
            map[i][j] = num;
            if (num == 2) {
                goal_row = i;
                goal_col = j;
            }
        }
    }
    
    // 거리 계산 BFS
    queue<Info> q;
    q.push(Info(goal_row, goal_col, 0));
    visited[goal_row][goal_col] = 1;
    
    while (!q.empty()) {
        Info v = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int n_row = v.r + drow[i];
            int n_col = v.c + dcol[i];
            int n_dist = v.dist + 1;
            // 범위 체크
            if (n_row < 0 || n_col < 0 || n_row >= row || n_col >= col)
                continue;
            // 방문안했으면서 갈 수 있는 곳
            if (visited[n_row][n_col] == 0 && map[n_row][n_col] != 0) {
                visited[n_row][n_col] = 1;
                dist[n_row][n_col] = n_dist;
                q.push(Info(n_row, n_col, n_dist));
            }
        }
    }
	// 정답 출력
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (visited[i][j] == 0 && map[i][j] == 1)
                cout << "-1" << " ";
            else
                cout << dist[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}