[Java] baekjoon_14940 : 쉬운 최단거리

그래프 이론, 그래프 탐색, 너비 우선 탐색

쉬운 최단거리 : Silver1

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

14940번: 쉬운 최단거리

 

 

이 문제는 주어진 지도에서 각 지점에서 목표 지점까지의 최단 거리를 구하는 문제이다.
지도는 가로와 세로로만 움직일 수 있다.
지도의 크기는 n × m이며, 입력에는 갈 수 없는 땅(0), 갈 수 있는 땅(1), 목표 지점(2)이 주어진다.
목표 지점은 단 한 곳이며, 이동할 수 있는 위치는 0 이상의 값을 가진다.

 

=> BFS 알고리즘을 활용하여 각 지점에서 목표 지점까지의 최단 거리를 계산하도록 했다.

 

 

풀이

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

public class Main {
  private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  
  static int n, m; // 가로와 세로의 크기를 나타내는 변수
  static int[][] map; // 입력된 지도를 나타내는 2차원 배열
  static int[][] dist; // 각 지점에서 목표 지점까지의 거리를 저장하는 배열
  static boolean[][] visited; // 방문 여부를 저장하는 배열
  static Queue<int[]> queue = new LinkedList<>(); // BFS 알고리즘을 위한 큐 (여기서 int[]는 좌표를 저장)
  static int[] dx = { 0, 1, 0, -1 }; // 상하좌우로 이동하기 위한 배열
  static int[] dy = { -1, 0, 1, 0 }; // 상하좌우로 이동하기 위한 배열

  public static void main(String[] args) throws IOException {
    StringTokenizer st = new StringTokenizer(br.readLine());
    n = Integer.parseInt(st.nextToken());
    m = Integer.parseInt(st.nextToken());

    map = new int[n][m];
    dist = new int[n][m];
    visited = new boolean[n][m];

    int startX = 0, startY = 0;

    // 지도 입력
    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) {
          startX = i;
          startY = j;
        }
      }
    }

    // BFS를 통해 각 지점에서 목표 지점까지의 거리 계산
    bfs(startX, startY);

    // 결과 출력
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (map[i][j] == 0) {
          bw.write("0 ");
        } else if (!visited[i][j]) {
          bw.write("-1 ");
        } else {
          bw.write(dist[i][j] + " ");
        }
      }
      bw.newLine();
    }
    bw.flush();
    br.close();
    bw.close();
  }

  // BFS 수행
  static void bfs(int x, int y) {
    queue.offer(new int[] { x, y });
    visited[x][y] = true;

    while (!queue.isEmpty()) {
      int[] cur = queue.poll();
      int curX = cur[0];
      int curY = cur[1];

      for (int i = 0; i < 4; i++) {
        int nextX = curX + dx[i];
        int nextY = curY + dy[i];

        if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m && map[nextX][nextY] != 0 && !visited[nextX][nextY]) {
          visited[nextX][nextY] = true;
          dist[nextX][nextY] = dist[curX][curY] + 1;
          queue.offer(new int[] { nextX, nextY });
        }
      }
    }
  }
}

 

ㄴ bfs 메서드는 BFS 알고리즘을 구현한 메서드로, 시작 지점부터 상하좌우로 탐색하면서 방문하지 않은 지점이면 큐에 추가하고 거리를 업데이트하도록 했다.

ㄴ 모든 지점에 대해 거리를 출력하되, 갈 수 없는 땅인 경우는 0을, 도달할 수 없는 위치는 -1을 출력하도록 했다.

 

bfs 메서드

1. 시작 지점을 큐에 추가하고 방문 여부를 표시한다.

queue.offer(new int[] { x, y });

 

ㄴ 시작 지점의 좌표를 큐에 추가한다.

visited[x][y] = true;

 

ㄴ 시작 지점을 방문했음을 표시한다.

 

2. 큐가 빌 때까지 아래의 과정을 반복한다.

while (!queue.isEmpty()) { ... }

ㄴ 큐가 비어 있지 않은 동안 반복한다.

 

 

3. 큐에서 한 지점을 꺼낸다.

int[] cur = queue.poll();

ㄴ 큐에서 한 지점의 좌표를 가져온다.
ㄴ 이 지점의 x 좌표를 curX, y 좌표를 curY에 저장한다.

 

 

4. 현재 지점에서 상하좌우로 이동한다.

for (int i = 0; i < 4; i++) { ... }

ㄴ 현재 지점에서 상하좌우로 이동한다.

 

 

5. 다음 위치가 유효하고, 이동할 수 있는 지점인지 확인한다.

int nextX = curX + dx[i];
int nextY = curY + dy[i];

ㄴ 다음 위치의 좌표를 계산한다.

if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m && map[nextX][nextY] != 0 && !visited[nextX][nextY]) { ... }

 

ㄴ 다음 위치가 지도 범위 내에 있고, 이동할 수 있는 지점인지 확인한다.

nextX >= 0 && nextX < n && nextY >= 0 && nextY < m

 

ㄴ 다음 위치가 지도 범위 내에 있는지 확인한다.

map[nextX][nextY] != 0

ㄴ 다음 위치가 갈 수 있는 지점인지 확인한다. (0이 아닌 값이면 갈 수 있는 지점)

!visited[nextX][nextY]

ㄴ 다음 위치를 방문하지 않았는지 확인한다.

 

6. 다음 위치를 큐에 추가하고 거리를 업데이트한다.

visited[nextX][nextY] = true;

ㄴ 다음 위치를 방문했음을 표시한다.

dist[nextX][nextY] = dist[curX][curY] + 1;

ㄴ 다음 위치까지의 거리를 업데이트한다.

queue.offer(new int[] { nextX, nextY });

 

ㄴ  다음 위치를 큐에 추가한다.

=> 이러한 과정을 통해 BFS 알고리즘을 사용하여 각 지점에서 목표 지점까지의 최단 거리를 계산할 수 있다.