[BOJ] BOJ_2178 미로 탐색 (JAVA)

[문제 - 2178번 미로 탐색]

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

 

[접근방식]

그래프 탐색 알고리즘 문제를 집중적으로 해결하고 싶어서 선택한 문제이다.

문제 자체는 많이 접해본 뉘양스가 느껴졌다.

이동가능한 칸은 1, 이동불가능한 칸은 0으로 표시되어 있는 배열이 있다.

좌측 상단 출발점(1,1) 에서 우측 하단 도착점(N, M)으로 이동가능한 최소 비용을 구하는 길찾기 문제 였다.

 

DFS / BFS 중 어떤 것을 사용해야 하는지 상당히 많은 시간을 고민하였다.

 

문제에서 "항상 도착위치로의 이동을 보장" 이라고 명시하였고, 문제에서 원하는 답이 "최소 비용" 이므로, "BFS" 를 선택했다.

 

BFS 방식의 핵심

1. 현재 노드에서 접근 가능한 노드를 Queue에 담아 순차적으로 이동한다.

2. 해당 노드가 이미 방문했는지를 판단하는 visited 배열을 사용하여, 방문하지 않는 노드로만 이동한다.

3. 이동 Cost 를 측정하기 위해, 같은 레벨의 노드를 모두 방문한 후에 Cost를 증가한다.

 

[Java Code]

/**
 * BOJ_미로 탐색
 * https://www.acmicpc.net/problem/2178
 */

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


public class Main {

  //상하좌우 이동
  static int[] dx = {-1, 1, 0, 0};
  static int[] dy = {0, 0, -1, 1};
  static int[][] map;
  static boolean[][] visited; //방문여부
  static int N, M;

  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    //N, M
    String[] s = br.readLine().split(" ");
    N = Integer.parseInt(s[0]);
    M = Integer.parseInt(s[1]);

    map = new int[N][M];
    visited = new boolean[N][M];

    //array
    for (int i = 0; i < N; i++) {
      String row = br.readLine();
      for (int j = 0; j < M; j++) {
        map[i][j] = row.charAt(j) - '0';
      }
    }


    bw.write(bfs(0, 0) + "\n");
    bw.flush();
    bw.close();
  } //main - end


  private static int bfs(int startX, int startY) {
    // 방문 가능한 노드를 담는 Queue
    Queue<int[]> queue = new LinkedList<>();

    //시작점 (1, 1) 출발 세팅
    queue.add(new int[]{startX, startY});
    visited[startX][startY] = true;

    int moves = 1;
    
    while (!queue.isEmpty()) {
      int size = queue.size();
      
      for (int i = 0; i < size; i++) {
        int[] current = queue.poll();
        int x = current[0];
        int y = current[1];

        //도착점 도착
        if (x == N - 1 && y == M - 1) return moves;

        //현재 위치에서 4방향 이동 가능 여부 판단
        for (int j = 0; j < 4; j++) {
          int nx = x + dx[j];
          int ny = y + dy[j];

          //이동 가능하고, 아직 방문하지 않는 노드이면 큐에 추가
          if (nx >= 0 && ny >= 0 && nx < N && ny < M && map[nx][ny] == 1 && !visited[nx][ny]) {
            visited[nx][ny] = true;
            queue.add(new int[]{nx, ny});
          }
        }
      }

      moves ++;
    }

    return -1;
  } //bfs - end


}

 

위에서 'BFS 방식의 핵심'을 정리하였다.

여기서 3번 'Cost 증가 방식' 이 개인적으로 가장 이해하고 구현하기에 까다로웠다.

같은 레벨의 노드를 모두 처리 후 비용 증가를 위한 반복문이다.

 

[Rewind]

1. 어려웠던 점

- BFS / DFS 해결 방식으로 선정하는 기준

- cost 증가 방식

 

2. 알게된 점

- BFS / DFS 해결 방식으로 선정하는 기준

- cost 증가 방식

 

3. 개선방안

- 그래프 탐색 문제를 더 풀어야 한다.