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

문제 링크입니다. https://www.acmicpc.net/problem/14940

14940번: 쉬운 최단거리

간단한 4방향 BFS 문제였습니다.

목표 지점이 2로 주어지고, 어느 점이든 목표 지점까지 갈 수 있는 최단 거리를 구하는 문제입니다.

최단 거리를 구하는 문제이기 때문에 DFS가 아닌 BFS로 풀어야 합니다.

 

목표 지점에서 역으로 출발해 어느 점이든 간의 최소 거리를 구하면 풀 수 있는 문제입니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <string>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second

using namespace std;

int N, M;
int map[1001][1001];
int check[1001][1001];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
P start;

void bfs(){
    queue<P> q;
    q.push(start);
    check[start.F][start.S] = 0;
    while(!q.empty()){
        int x = q.front().F;
        int y = q.front().S;
        q.pop();
        for(int i = 0; i < 4; i++){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(xx >= 1 && xx <= N && yy >= 1 && yy <= M){
                if(map[xx][yy] == 1 && check[xx][yy] == -1){
                    q.push({xx,yy});
                    check[xx][yy] = check[x][y] + 1;
                }
            }
        }
    }
}

void solve(){
    memset(check, -1, sizeof(check));
    bfs();
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            if(map[i][j] == 0) cout << "0" << " ";
            else cout << check[i][j] << " ";
        }
        cout << "\n";
    }
    
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cin >> map[i][j];
            if(map[i][j] == 2) start = {i,j};
        }
    }
    solve();
    return 0;
}

 

질문 및 조언은 댓글 남겨주세요!