[PS] 99클럽 코테 스터디 35일차 TIL (게임 맵 최단거리)

문제

문제 링크

설명

장애물(위 사진에서 검은 영역) 을 피해 그래프 좌측 최상단(0,0) 에서 우측 최하단(n, m) 까지 가는 최단 경로를 구하는 문제.

풀이

최단 경로 탐색을 위해 bfs 로 풀었다. 문제에서 입력으로 그래프 2차원 배열이 주어진다. bfs 함수 에서는 다음과 같은 작업을 해야 한다.

• 현재 좌표 방문 처리
• 경계 조건 처리(isInRange)
• 갈 수 있는 좌표로 이동 시 카운트 증가 (depth + 1)
• 종료 조건:
  • 문제에서 우측 최하단(n, m) 에 도달하는 경우
  • 그 최단경로를 요구하고 있으므로 해당 좌표값에 도달하면 좌표 이동 간 누적된 depth 값을 반환해 준다.

참고로, 매번 아래와 같은 경계 확인 로직을 반복적으로 작성하기 귀찮다면 Boundary Padding 방법을 쓸 수 있다.

 private static boolean isInRange(int x, int y) {
    return x >= 0 && x < graph.length && y >= 0 && y < graph[0].length;
  }

이런 문제를 풀 때, 그래프 좌표 값 세팅 시 경계에 부딪힐 것을 미리 고려해 index 1 부터 값을 세팅하고, 끝 인덱스도 넉넉하게 1이상 더 크게 선언한다. 예를 들어 다음과 같은 방식으로 graph 를 선언하고, 세팅해 줄 수 있다.

// graph 크기를 애초에 넉넉하게 잡는다.
graph = new int[n + 2][n + 2];

// index 1 부터 넣어준다.
for (int i = 1; i <= N; i++) {
  String[] split = br.readLine().split("");
  for (int j = 1; j <= M; j++) {
    graph[i][j] = Integer.parseInt(split[j - 1]);
  }
}

최대 입력으로 들어오는 길이가 1000 이하면 그냥 1000 + 10 정도로 선언해도 크게 문제없다. 단, 입력으로 들어오는 길이가 1000 이상을 훨씬 넘어간다면 int[][] 같은 2차원 배열 보단 ArrayList<Integer>[] 로 선언해야 한다. 이렇게 선언하면 상하좌우 탐색 시 경계를 벗어나는 경우란 있을 수 없으므로 isInRange 같은 조건을 매번 확인할 필요가 없다.

class Solution {
  static int[][] graph;
  static boolean[][] visited;
  static int[] dx = {-1, 1, 0, 0};
  static int[] dy = {0, 0, -1, 1};

  public int solution(int[][] maps) {
    graph = maps;
    visited = new boolean[graph.length][graph[0].length];

    return bfs();
  }

  private int bfs() {
    Queue<int[]> queue = new LinkedList<>();
    queue.add(new int[] {0, 0, 1});
    visited[0][0] = true;

    while (!queue.isEmpty()) {
      int[] current = queue.poll();
      int x = current[0];
      int y = current[1];
      int depth = current[2];

      if (x == graph.length - 1 && y == graph[0].length - 1) {
        return depth;
      }

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

        if (isInRange(nx, ny) && !visited[nx][ny] && graph[nx][ny] != 0) {
          queue.add(new int[] {nx, ny, depth + 1});
          visited[nx][ny] = true;
        }
      }
    }
    return -1;
  }

  private static boolean isInRange(int x, int y) {
    return x >= 0 && x < graph.length && y >= 0 && y < graph[0].length;
  }
}