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

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

14940번: 쉬운 최단거리

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M;
int arr[1001][1001];
int visited[1001][1001];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
queue<pii>q;

void bfs()
{
    while(!q.empty())
    {
        auto [y, x] = q.front();
        q.pop();

        for(int i=0; i<4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny >= N || nx >= M || ny < 0 || nx < 0) continue;
            if(visited[ny][nx] || !arr[ny][nx]) continue; //방문여부랑 갈수없는 위치인지 체크
            visited[ny][nx] = visited[y][x] + 1;
            q.push({ny, nx});
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> M;
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            cin >> arr[i][j];
            if(arr[i][j]==2) 
            {
                q.push({i,j}); //시작 위치
                visited[i][j] = 1; //방문 처리
            }
        }
    }

    bfs();

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            cout << (arr[i][j]==0 ? 0 : visited[i][j]-1) << " "; //0이면 0, 아니면 현재값 -1 (시작을 1로 했기 떄문)
        }
        cout << "\n";
    }
    
    return 0;
}

기본적으로 bfs을 통해 풀 수 있는 문제이다.

목표 지점이 사실상 출발 위치인 것을 이용해 2일 때를 기준으로 bfs 탐색을 돌려준다.

 

출발 지점을 1로 시작해서 카운팅했기 때문에 나중에 출력은 -1을 해서 해준다.

 

해당 문제에서 원래 갈 수 있는 땅 부분이지만 목표 지점으로 도달할 수 없는 위치는 -1을 출력하도록 되어있는데,

이는 아래와 같은 케이스다.

2 1 1 1
1 0 0 0
1 0 0 1

오른쪽 하단의 1의 경우는 벽(0)으로 둘러쌓여있기 때문에 땅이지만 2로 이동은 불가하다.

이 경우엔 애초에 bfs 탐색을 돌 때 해당 위치로 가지 못하므로 visited배열에는 처음값인 0이 변동없이 그대로 유지된다.

여기에 출력할때 -1을 해주기에 위 조건 또한 자연스럽게 해결된다.