게임 맵 최단거리(Lv.2)

 

---

 

문제 설명

 

 

 

입출력 예시

 

 

요약

상대 진영에 도착하는 최단거리 구하기(막혀있으면 -1 return)

 

---

 

풀이

 

접근 방식

1. 주어진 이차원 배열 형태로 미로 구성

  → 미로 전체를 둘러싸기 위해 행과 열의 크기에 각각 2를 더한 만큼의 maze(boolean 2차원 배열) 생성

  → 행의 개수, 열의 개수 만큼 이중 반복문을 통해 maze에 미로 표시

 

2. bfs를 활용해 최단 경로 구하기

  → 상하좌우로 이동할 수 있는 좌표가 담긴 directions (int 2차원 배열) 생성

  → 현재 좌표와 이동한 거리를 인스턴스로 갖는 Position 클래스 객체를 큐에 담아 FIFO 방식으로 확인

 

---

 

코드리뷰

 

import java.util.*;

// 현재 좌표(row, col)와 이동한 거리(dist)를 인스턴스로 갖는 Position 클래스 객체
class Position{
    int row;
    int col;
    int dist;
    public Position(int row, int col, int dist) {
        this.row = row;
        this.col = col;
        this.dist = dist;
    }
}

class Solution {
    int N;
    int M;
    boolean[][] maze;
    boolean[][] visited;
    int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};	// 상, 하, 좌, 우 이동을 위한 배열
    List<Position> list = new ArrayList<>();	// Queue로 사용할 list

    public int bfs(int row, int col) {	// 너비 우선 탐색 메소드
        visited[row][col] = true;	// 첫 시작 좌표를 방문했음으로 마킹
        list.add(new Position(row, col, 1));	// 처음 위치의 좌표(1, 1)와 거리(1)를 객체에 저장 후 큐에 담는다.

        while(!list.isEmpty()) {	// 큐에 객체가 남아있지 않을 때 까지 반복 실행
            Position objOut = list.remove(0);	// 큐에서 첫 번째(index = 0) Position 객체 꺼내기
            if(objOut.row == N && objOut.col == M) {	// 마지막 지점에 도달했다면
                return objOut.dist;	// 꺼낸 Position 객체의 dist(이동한 거리) 리턴
            }
            for(int i = 0; i < 4; i++) {	// 해당 좌표의 상하좌우 탐색 후 조건에 맞으면 모두 큐에 삽입(bfs)한다.
                int newRow = objOut.row + directions[i][0];	// 상, 하
                int newCol = objOut.col + directions[i][1];	// 좌, 우
                if(!visited[newRow][newCol] && maze[newRow][newCol]) {	// 방문하지 않았고 길이 존재하면
                    visited[newRow][newCol] = true;	// 방문하고 마킹
                    list.add(new Position(newRow, newCol, objOut.dist+1));	// 큐에 삽입
                }
            }
        }
        return -1;	// 마지막 지점에 도달하지 못했다면 -1 return
    }

    public int solution(int[][] maps) {
        N = maps.length;	// 행의 개수
        M = maps[0].length;	// 열의 개수
        maze = new boolean[N+2][M+2];	// 주어진 maps 배열을 감싸기 위해 행과 열 각각 2씩 더하기
        visited = new boolean[N+2][M+2];	// 방문확인을 위한 배열

        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if(maps[i][j] == 1) {
                    maze[i+1][j+1] = true;	// maze는 maps 바깥으로 한 겹이 더 둘러져 있는 형태기 때문에 [i+1][j+1] 좌표를 true로 바꿈
                }
            }
        }
        int answer = bfs(1, 1);	// bfs 시작(시작 지점은 (1, 1)로 고정)
        return answer;
    }
}

 

---

 

추가 자료

 

[N+2][M+2] 크기로 설정한 maze 배열

상하좌우 탐색에서 map을 벗어나는 경우를 방지

 

 

 

움직인 거리(dist)와 큐에 들어온 순서

큐에는 상하좌우 순서로 담긴다

 

 

 

* refs

https://www.youtube.com/watch?v=yQ7o1Y7X_Rg