Lv.2 [너비우선탐색] - 게임 맵 최단거리 (풀이 미완성)

---

[ 문제 링크 ]

프로그래머스 Lv2. 게임 맵 최단거리

 

[ 문제 설명 이미지 ]

 

게임 맵 최단거리

미로의 시작 점에서 시작해서 목적지까지 찾아가는 최단 거리를 구하는 문제이다.
최단거리 탐색 중 BFS - 너비우선 탐색에 대한 전형적인 문제이다.
현재 시점에 움직일 수 있는 여러가지 경우의 수 중 모든 경우를 다 확인해야 한다.
맵에서 player가 특정 위치에 있을 때 대각선을 제외한 이동가능 경우의 수는 4가지 경우의 수가 나온다.
이 4가지 경우를 모두 가본다.
각 방향대로 1칸씩 움직인 이후에 다음 위치를 경우의 수 대로 생각하는 방식이다.
현재 시작점 위치를 0으로 두고 각각의 이동할 수 있는 경우의 수를 모두 가보는 것이다.
현재 위치의 수보다 1씩 더해서 이동하게 된다.
만약 벽이 있다면 못간다.
이동한 이후에 해당 위치에서 또 이동할 수 있는 모든 경우의 수를 이동해본다.
이미 왔던 방향 혹은 가장자리 방향의 경우 이동할 수 없게 된다.

위와 같이 이동할 수 있는 모든 경우의 수를 모두 확인해준다.
이러한 너비,깊이 우선 탐색은 한번에 여러값이 움직이므로 복잡하게 느껴질 수 있다.
데이터 값이 어떻게 변하는지 추적하면 이해하기 매우 어렵다.
따라서 모든 경우에 똑같이 적용할 수 있는 조건만 생각하고 종료조건만 잘 설정하면 된다.

1. 네 방향으로 한 칸씩 이동한다.
2. 이동한 후에는 현재 값보다 1 큰 값을 채운다.
3. 벽, 미로 밖, 왔던길로 못간다.

종료 조건 : 이동후 위치가 목적지 일 경우.

BFS

Queue

---

[풀이 1] 

class Solution {
    class Position {
        int x, y; /* X는 가로(열) / Y는 세로(행) */

        /**
         * 바깥이아닌지 여부 확인
         * @return 바깥이 아니면 false 바깥이면 true
         */
        boolean isValid(int width, int height) {
            if (x<0 || x >= width) return false;
            if (y<0 || y >= height) return false;
            return true;
        }

        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public int solution(int[][] maps) {

        /* 이동 거리를 구해야 하므로 count값을 구해야한다.*/
        int mapHeight = maps.length; // 세로
        int mapWidth = maps[0].length; // 가로
        int [][] count = new int[mapHeight][mapWidth];
        count[0][0] = 1; //시작 위치 초기화

        /* 지나온 길인지 확인하기 위한 visit 배열을 만든다. */
        boolean[][] visited = new boolean[mapHeight][mapWidth];
        visited[0][0] = true; // 시작위치는 이미 지나온곳 이므로 true로 초기화

        Queue<Position> queue = new LinkedList<>(); //BFS : Queue

        queue.offer(new Position(0,0));
        while(!queue.isEmpty()) {
            Position current = queue.poll();

            int currentCount = count[current.y][current.x]; //현재위치까지 count한 총 거리값

            // 4가지 경우 queue에 삽입 - 매 루프마다 해당 queue값을 꺼내서 동일한 작업을 한다.
            final int[][] moving = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
            for(int i = 0; i < moving.length; i++) {
                /**
                 * 이동하게 될 위치 초기화
                 * x(열), y(행)-1 ↑(위쪽으로 한칸 이동)
                 * x(열), y(행)+1 ↓(아래쪽으로 한칸 이동)
                 * x(열)-1, y(행) ←(왼쪽으로 한칸 이동)
                 * x(열)+1, y(행) →(오른족으로 한칸 이동)
                 */
                Position moved = new Position(current.x + moving[i][0], current.y + moving[i][1]);
                /**
                 * 이동할 위치 기준 (바깥이아닌경우 / 벽이 아닌경우 / 방문하지 않은경우)에만 이동 처리
                 * 검증 순서는 배열의 인덱스가 -1이 되서는 안되기 때문에 우선 바깥여부인지 먼저 체크해야한다.
                 * 바깥 여부라면 한번도 이동하지 않은 상태이기 때문에 인덱스가 0이다.
                 * 만약 바깥여부에 대한 검증이 지나갔다면 인덱스가 0 이상이므로 뒤(왼쪽 혹은 위) 로 갈수가 있게 된다.
                 */
                if(!moved.isValid(mapWidth, mapHeight) || maps[moved.y][moved.x] == 0 || visited[moved.y][moved.x]) continue; // 반대일경우 어느 하나라도 만족하지 않으므로
                count[moved.y][moved.x] = currentCount + 1; // 현재위치로부터 이동할위치로 1칸 이동하므로 총 거리값인 count를 1 증가시킨다.
                visited[moved.y][moved.x] = true; // 이동한 위치의 방문여부를 true로 체크한다
                queue.offer(moved); // Position을 다음값으로 이동시킨다.
            }
        }
        int answer = count[mapHeight-1][mapWidth-1];
        if (answer == 0) return -1;
        return answer;
    }
}

 

---