baekjoon 14940. 쉬운 최단거리

쉬운 최단거리

문제 출처

2017 Sogang Programming Contest > Master F번

풀이

목표 지점에서 한칸씩 멀어질수록 1씩 증가시켜주되, 갈 수 없는 땅을 주의해서 계산해야 합니다.
오직 가로 세로로만 움직일 수 있으므로, 상하좌우 BFS를 이용하면 쉽게 거리를 구해낼 수 있습니다.

반복문을 통한 입력에서 현재 입력받는 숫자가 목표 지점인 2라면 해당 인덱스를 targetX, targetY로 설정합니다. 편의를 위해 2차원 배열에서 첫번째 인덱스가 열(Y)인 점을 고려하여 첫번째 반복문의 인덱스 i와 두번째 반복문의 인덱스 j를 각각 targetY = i, targetX = j로 설정합니다.

목표 지점으로 부터 상하좌우 한칸씩 반복문을 돌며 범위에 벗어나거나 원래 갈 수 없는 땅을 제외하고 해당 칸을 방문하지 않았다면 queue에 삽입하여 BFS를 돌게 합니다. 각 칸의 거리는 visited[1001][1001] 배열을 이용하여 저장합니다. 칸마다 1씩 증가하면 되는 간단한 연산이므로, 다음과 같이 BFS 내부에서 거리를 구할 수 있습니다.

if(ny >= 0 && ny < N && nx >= 0 && nx < M) {
    if(!visited[ny][nx] && num[ny][nx] != 0) {
        visited[ny][nx] = visited[y][x] + 1;
        q.push({ny, nx});
    }
}

원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력해야하므로, 목표지점을 1로 설정하여 거리를 계산하고, 출력 시 -1을 더해주면 원하는 출력을 얻을 수 있습니다.

전체 코드

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

int N, M;
int num[1001][1001];
int visited[1001][1001];
int targetY, targetX;

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

void bfs(int startY, int startX) {
    queue<pair<int, int>> q;
    q.push({startY, startX});
    visited[startY][startX] = 1;

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

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

            if(ny >= 0 && ny < N && nx >= 0 && nx < M) {
                if(!visited[ny][nx] && num[ny][nx] != 0) {
                    visited[ny][nx] = visited[y][x] + 1;
                    q.push({ny, nx});
                }
            }
        }
    }
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    cin >> N >> M;

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> num[i][j];
            if(num[i][j] == 2) {
                targetY = i;
                targetX = j;
            }
        }
    }

    bfs(targetY, targetX);

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(num[i][j] == 0) cout << 0 << ' ';
            else cout << visited[i][j] - 1 << ' ';
        }
        cout << '\n';
    }

    return 0;
}