백준 14940번 [쉬운 최단거리](C++) -yes6686- 티스토리

백준 문제 풀이: 14940 [쉬운 최단거리]

---

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

문제 설명:

2차원 격자에서 목표 지점(값이 2인 위치)에서 다른 모든 도달 가능한 칸까지의 최단 거리를 구하는 문제입니다. 벽(값이 0인 칸)은 이동할 수 없으며, 도달할 수 없는 칸은 -1로 표시합니다.

---

문제 해결 코드

// 백준 14940 - 쉬운 최단거리
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int arr[1001][1001]; // 입력 맵
int ans[1001][1001]; // 최단 거리 결과
int dx[4] = {0, 0, 1, -1}; // 이동 방향 (상, 하, 좌, 우)
int dy[4] = {1, -1, 0, 0};
int n, m; // 격자의 크기
queue<pair<int, int>> q; // BFS를 위한 큐

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

        // 상하좌우 이동
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 격자 범위를 벗어나거나 벽이거나 이미 방문한 경우
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (arr[nx][ny] == 0 || ans[nx][ny] != -1) continue;

            ans[nx][ny] = ans[x][y] + 1; // 최단 거리 갱신
            q.push({nx, ny}); // 큐에 추가
        }
    }
}

int main() {
    cin >> n >> m;

    // 입력 및 초기화
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
            ans[i][j] = -1; // 초기값 -1로 설정
            if (arr[i][j] == 2) { // 목표 지점(2인 위치)
                ans[i][j] = 0; // 시작점의 거리는 0
                q.push({i, j}); // BFS 시작 위치
            }
        }
    }

    bfs(); // BFS 수행

    // 결과 출력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (arr[i][j] == 0) { // 벽일 경우 0 출력
                cout << 0 << ' ';
            } else {
                cout << ans[i][j] << ' ';
            }
        }
        cout << '\n';
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘:
  • BFS(너비 우선 탐색)를 사용하여 목표 지점에서 다른 칸까지의 최단 거리를 계산합니다.
• 구현 세부사항:
  • 격자의 각 칸을 초기화하고 목표 지점을 큐에 추가하여 BFS를 시작합니다.
  • BFS를 통해 상하좌우로 확장하며, 방문하지 않은 칸의 거리를 갱신합니다.
  • 도달할 수 없는 칸은 초기값인 -1로 유지됩니다.
  • 벽은 항상 0으로 출력됩니다.
• 시간 복잡도 분석:
  • 격자의 크기를 n × m이라 할 때, 모든 칸을 한 번씩 방문하므로 BFS의 시간 복잡도는 O(n × m)입니다.

---

결과

제출 시, 모든 테스트 케이스에 대해 올바른 결과를 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!