[BaekJoon] 14940번 - 쉬운 최단거리 [Java][C++]

문제 링크

---

1. 문제 풀이

각 지점에서 목표지점까지의 최단 거리를 구하는 문제로 목표지점부터 각 지점까지의 거리를 BFS를 이용해서 구하는 방식으로 해결할 수 있다. 이때 최단 거리가 아닌 좌표별 거리를 구해야하므로 2차원 배열을 활용해서 큐에 넣는 다음 노드의 좌표에 대해 거리를 갱신해주는 방식으로 해결했다. 2차원 거리 배열은 갈 수 없는 땅과 목표지점은 $0$ 으로 나머지 땅은 $-1$ 로 초기화한 후 계산해야 하는데 마침 갈 수 있는 땅이 $1$ 로 주어져 있으므로 지도의 부호를 뒤집은 값으로 초기화해줬다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {

    static final int[] dr = {-1, 0, 1, 0};
    static final int[] dc = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] map = new int[n][m];
        int sr = -1;
        int sc = -1;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 2) {
                    sr = i;
                    sc = j;
                }
            }
        }

        int[][] result = bfs(sr, sc, n, m, map);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                sb.append(result[i][j]).append(" ");
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }

    static int[][] bfs(int sr, int sc, int n, int m, int[][] map) {
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{sr, sc});

        boolean[][] visited = new boolean[n][m];
        visited[sr][sc] = true;

        int[][] dist = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dist[i][j] = -map[i][j];
            }
        }
        dist[sr][sc] = 0;

        while (!q.isEmpty()) {
            int size = q.size();

            while (size-- > 0) {
                int[] node = q.poll();

                for (int d = 0; d < 4; d++) {
                    int nr = node[0] + dr[d];
                    int nc = node[1] + dc[d];

                    if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                    if (map[nr][nc] == 0 || visited[nr][nc]) continue;

                    q.offer(new int[]{nr, nc});
                    visited[nr][nc] = true;
                    dist[nr][nc] = dist[node[0]][node[1]] + 1;
                }
            }
        }

        return dist;
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

int n, m;
int grid[1000][1000];
bool visited[1000][1000];
int dist[1000][1000];

void bfs(int sr, int sc) {
    queue<pair<int, int>> q;
    q.push({sr, sc});

    visited[sr][sc] = true;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            dist[i][j] = -grid[i][j];
        }
    }
    dist[sr][sc] = 0;

    while (!q.empty()) {
        int sz = q.size();

        while (sz--) {
            auto [r, c] = q.front();
            q.pop();

            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d];
                int nc = c + dc[d];

                if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                if (grid[nr][nc] == 0 || visited[nr][nc]) continue;

                q.push({nr, nc});
                visited[nr][nc] = true;
                dist[nr][nc] = dist[r][c] + 1;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    int sr = -1;
    int sc = -1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];

            if (grid[i][j] == 2) {
                sr = i;
                sc = j;
            }
        }
    }

    bfs(sr, sc);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << dist[i][j] << ' ';
        }
        cout << '\n';
    }
}

---