14940번 : 쉬운 최단거리 [C++]

문제 링크

성공 여부(걸린 시간): 성공(27분)

아이디어

도착지는 2로 표시되어있고 하나이다.
그리고 구해야 하는 것은 해당 도착지까지 도달하는 데에 최단거리

*다르게 말하면 *

도착지에서 각 각의 위치까지 도달하는데 걸리는 거리를 구하면 된다.
그렇게 하면 한번의 BFS로도 정답을 구할 수 있다.

BFS를 돌때는 해당 배열에 대한 visited배열의 값이 지금 방문이 더 가까운지에 대해서 검사하고
그렇다면 갱신 아니라면 그냥 continue

근데 문제를 제대로 안읽어서
만약에 못도착하는 곳인데 원래 못도착하는 곳이면(장애물이 있는 곳) 0
그것이 아니면 -1로 표시를 해뒀어야 했는데 그걸 안해줘서 시간을 끌었다...

풀이 코드

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

static int N, M;
bool canGo(int x, int y) {
    return x < N && y < M && x >= 0 && y >= 0;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> N >> M;
    vector<vector<int>> map(N, vector<int>(M, 0));
    vector<vector<int>> visited(N, vector<int>(M, 0xFFFFFF));

    pair<int, int> start;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
            if (map[i][j] == 2) {
                start = { i, j };
            }
        }
    }

    queue<pair<int, int>> q;
    q.push(start);
    visited[start.first][start.second] = 0;

    int dx[] = { 1, 0, -1, 0 };
    int dy[] = { 0, 1, 0, -1 };

    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        int x = cur.first;
        int y = cur.second;
        for (int dir = 0; dir < 4; dir++) {
            int mx = dx[dir] + x;
            int my = dy[dir] + y;
            if (canGo(mx, my) && map[mx][my] == 1 && visited[x][y] + 1 < visited[mx][my]) {
                q.push({ mx, my });
                visited[mx][my] = visited[x][y] + 1;
            }
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            int result = visited[i][j] == 0xFFFFFF ? map[i][j]==0?0:-1 : visited[i][j];
            cout << result;
            if (j != M - 1) {
                cout << " ";
            }
        }
        if (i != N - 1) {
            cout << "\n";
        }
    }
    return 0;
}