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

백준 14940 : 쉬운 최단거리

난이도 : 실버 1

시간 : 25분 소요

 

 

문제

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

14940번: 쉬운 최단거리

풀이 과정

이 문제는 특정 정점으로부터의 거리를 구하면 되는 문제이다.

따라서 특정 정점의 이웃부터 모두 검사하는 넓이 우선 탐색이 필요한 문제이다.

또한, 각각의 정점마다 상하좌우로 4번을 검사해야 하기 때문에 ud[4] 배열과 lr[4] 배열을 사용하였다.

 

특정 정점으로부터 각각의 정점의 거리를 저장하기 위해 result 라는 2차원 배열을 새로 만들었다.

 

2차원 배열을 큐에 넣고 빼기를 쉽게 하기 위해 pair 자료형을 사용하였다.

 

 

 

최종 코드

#include <iostream>
#include <queue>
#define MAX 1001

using namespace::std;

int n,m;
int board[MAX][MAX];
int result[MAX][MAX];
int visited[MAX][MAX];
int a,b;
int ud[4] = {1,-1 ,0 ,0};
int lr[4] = {0 ,0 ,1 ,-1};

void bfs(int x, int y){
    queue<pair<int, int>> q;
    pair<int, int> p;
    visited[x][y] = 1;
    result[x][y] = 0;
    board[x][y] = 0;
    p = {x,y};
    q.push(p);
    
    while(!q.empty()){
        int t1 = q.front().first;
        int t2 = q.front().second;
        q.pop();
        
        for(int i=0; i<4; i++){
            int nx = t1+ud[i];
            int ny = t2+lr[i];
            
            if(nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
                if(visited[nx][ny] == 0 && board[nx][ny] != 0){  // 방문 x
                    visited[nx][ny] = 1;
                    result[nx][ny] = 1 + result[t1][t2];
                    pair<int, int> tmp;
                    tmp = {t1+ud[i], t2+lr[i]};
                    q.push(tmp);
                }
            }
        }
    }
    
}

int main(){
    scanf("%d %d", &n, &m);
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            scanf("%d", &board[i][j]);
            if(board[i][j] == 2){
                a = i;
                b = j;
            }
        }
    }
    bfs(a,b);
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(visited[i][j] == 0 && board[i][j] != 0){
                printf("-1 ");
            }else{
                printf("%d ", result[i][j]);
            }
        }
        printf("\n");
    }
}