since 2019.

1 minute read

Updated:

문제 설명

미로의 시작점에서 시작해서 목적지까지 찾아가는 최단 거리를 구하라.

제한 사항

  • maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
    • n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
  • maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
  • 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

구현 방법

  • 현재 시점에서 움직일 수 있는 여러 경우의 수가 있는데, 전체적으로 모든 경우를 다 확인하는 방식으로 해결한다. 즉 너비 우선 탐색을 활용한다.
  • 너비 우선 탐색, 깊이 우선 탐색은 한꺼번에 여러 값이 움직이므로 복잡하게 느껴질 수 있다. 데이터 값이 어떻게 변하는 지 추적하면 이해하기가 매우 어렵다. 따라서 모든 경우에 똑같이 적용할 수 있는 규칙만 생각하고 종료 조건만 잘 세우면 된다.
  1. 네 방향으로 한 칸씩 이동한다.
  2. 이동한 후에는 현재값보다 1 큰 값을 채운다.
  3. 벽, 미로 밖, 왔던 가지 못한다.
    • 종료 조건 : 이동 후 위치가 목적지이다.
  • 데이터 크기가 100 이하이므로 시간 복잡도는 생각하지 않아도 된다. 최단 거리를 찾는데 시간 제한을 고려하지 않아도 될 때 완전 탐색을 쓸 수 있다. DFS와 BFS 둘다 사용 가능하지만, BFS를 사용하면 최초로 도달한 깊이를 찾는 순간 바로 탐색할 수 있으므로 결과를 좀더 빠르고 간편하게 찾을 수 있다.

구현 코드

import java.util.*;

class Solution {
    //상하좌우를 탐색하기 위한 배열 선언하기
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static boolean[][] visited; // 방문 기록 저장 배열
    static int row, column;

    public int solution(int[][] maps) {
        int row = maps.length;
        int column = maps[0].length;

        visited = new boolean[row][column];
        
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {0, 0}); // 큐 자료구조에 시작 노드 삽입하기
        visited[0][0] = true;
        
        while(!queue.isEmpty()){    // 큐가 비어있을 때까지 반복
            int now[] = queue.poll();   // 큐에서 노드 데이터를 가져오기(poll 연산)
            for (int k=0; k < 4; k++){  // 상하좌우 탐색
                int x = now[0] + dx[k];
                int y = now[1] + dy[k];
                if(x >= 0 && y >= 0 && x < row && y < column) { // 좌표 유효성 검사하기
                    if(maps[x][y] !=0 && !visited[x][y]) { // 이동할 수 있는 칸이면서 방문하지 않은 노드
                        visited[x][y] = true;
                        maps[x][y] = maps[now[0]][now[1]] + 1;
                        queue.add(new int[] {x, y});
                    }
                }
            }
        }

        int answer = maps[row-1][column-1];
        if(answer == 1) answer = -1;
        return answer;
    }
}

You may also enjoy