백준 14940 쉬운 최단거리 (C++)

안유태·2023년 9월 24일
0

알고리즘

목록 보기
149/239
post-custom-banner

14940번: 쉬운 최단거리

bfs를 이용한 문제이다. 로직은 간단하다. 목표 지점의 좌표를 구해 bfs를 시작하여 카운트를 해주면서 저장을 해준 뒤 갈 수 있는 땅인데 카운트가 0인 곳은 -1로 바꿔주고 목표 지점의 카운트를 0으로 바꿔준 뒤 출력해주면 된다. 처음에 문제를 제대로 읽지 않아 -1로 출력해야 하는 점을 간과하여 시간 낭비를 많이 하였다. 문제를 잘 읽도록 하자.



#include <iostream>
#include <queue>

using namespace std;

int n, m, ty, tx;
int A[1000][1000];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int result[1000][1000];

void bfs() {
    queue<pair<pair<int, int>, int>> q;

    q.push({ { ty,tx },0 });

    while (!q.empty()) {
        int y = q.front().first.first;
        int x = q.front().first.second;
        int c = q.front().second;

        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            int nc = c + 1;

            if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
            if (A[ny][nx] == 0) continue;
            if (result[ny][nx] != 0) continue;

            q.push({ { ny,nx }, nc });
            result[ny][nx] = nc;
        }
    }
}

void solution() {
    bfs();

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (result[i][j] == 0 && A[i][j] != 0) 
                result[i][j] = -1;
        }
    }
    result[ty][tx] = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << result[i][j] << " ";
        }
        cout << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> A[i][j];

            if (A[i][j] == 2) {
                ty = i;
                tx = j;
            }
        }
    }

    solution();

    return 0;
}
profile
공부하는 개발자
post-custom-banner

0개의 댓글