99클럽 코테 스터디 12일차 TIL 게임 내 맵 최단거리

 

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

 

1. 문제 및 접근

 

2차원 배열로 양 끝(시작과 끝)에서 서로 시작하는데, 상대방 진형에 먼저 도착하면 이기는 게임

검은 색 벽이 존재하고 흰색 길로만 갈 수 있다.

움직일 땐 동서남북 넷 중 하나로 움직이고, 맵 범위를 넘어갈 순 없다.

만약 가는 도착할 수 없다면 -1을 return

가능한 경로 중 최단 거리의 이동횟수를 return 해라

 

 

 

제한 사항

 

maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.

n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.

maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.

처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

 

 

 

 

우선 dfs와 bfs를 떠올렸는데, 나는 dfs가 익숙해서 dfs로 모든 경로를 다 탐색한다고 생각했는데,,

bfs가 최단거리는 더 유리할 수 있다.

 

 

 

 

 

2. BFS

 

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

 

 

 

 

생각해보면 DFS의 경우 처음으로 발견한 길이가 최단거리가 아닐 수 있다.

그렇지만 BFS로 탐색할 경우 처음 발견한 게 무조건 최단거리이기에 

 

 

 

 

간단하게 DFS와 BFS를 비교하자면,

 

DFS와 BFS의 차이

 

 

 

 

 

 

 

DFS

• 현재 정점에서 가능한 제일 깊게 내려가는 깊이우선탐색
• Stack 또는 재귀함수로 구현

 

BFS

• 현재 정점에서 가까운 정점들부터 탐색하는 너비우선탐색
• Queue를 이용해서 구현

 

 

 

 

 

3. 풀이

 

private static final int[][] movement = new int[][]
        {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
//  왼  ,    오  ,    위   ,   아래
private static boolean[][] isVisited;


public static void main(String[] args) {
    int[][] arr = new int[][]
            {
                    {1, 0, 1, 1, 1},
                    {1, 0, 1, 0, 1},
                    {1, 0, 1, 1, 1},
                    {1, 1, 1, 0, 1},
                    {0, 0, 0, 0, 1}};
    게임맵최단거리bfs sol = new 게임맵최단거리bfs();
    System.out.println(sol.solution(arr));

}

private int solution(int[][] maps) {
    int n = maps.length;
    int m = maps[0].length;

    isVisited = new boolean[n][m];

    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[]{0, 0}); // 큐에 시작 위치를 넣기
    int answer = 1; // 시작지점도 하나로 시작
    isVisited[0][0] = true; // 시작 지점을 방문했다고 표시

    while (!queue.isEmpty()) { // 큐가 비어있지 않으면 계속함
        int size = queue.size(); // 큐에 들어있는 값들만큼 돌아야함
        for (int i = 0; i < size; i++) { // 가능한 상하좌우들을 돌고 가능하다면 그 거리는 추가해주기
            int[] now = queue.poll();
            int x = now[0];
            int y = now[1];

            if (x == n - 1 && y == m - 1) { // x,y가 끝까지 도착한 경우라면 ? answer을 return
                return answer;

            }

            for (int[] move : movement) { // 네 방향씩 탐색 (상하좌우)로 계속 탐색
                int toX = x + move[0];
                int toY = y + move[1];


                if (n > toX && m > toY && toX >= 0 && toY >= 0) {
                    if (!isVisited[toX][toY] && maps[toX][toY] == 1) {


                        // 조건이 좀 많긴 한데, 방문할 곳이
                        // 1. 방문한 적이 없어야 하고,
                        // 2. 벽이 아니여야 하고 (1이여야함)
                        // 3. 0보다 크거나 같고 배열의 크기보다 작아야함 (배열 범위 안)
                        queue.offer(new int[]{toX, toY}); //만족한다면 queue에 넣어주고 (담 탐색이 되니까)
                        isVisited[toX][toY] = true; // 방문했다고 표시
                    }
                }

            }
        }
        answer++; // 다 돌았으면 answer에 +1

    }
    return -1; // 다 돌았는데 안되면 -1 리턴
}

 

 

 

 

3-1 필요한 요소

 

 

 

 

먼저 움직일 수 있는 건 상, 하, 좌, 우로 움직일 수 있기에 2차원 배열에 담아줬다.

 

탐색 여부를 판별하는 배열도 만들어줬는데 (1차원으로도 가능하려나..)

 

 

 

 

배열의 x,y의 size를 받아서 isVisited을 만들어주고,

 

움직일 곳의 좌표를 저장하는 Queue를 구현해주고 시작점을 넣어주기

 

처음에 초기 조건들은 시작점은 방문했으니, true와 움직임을 나타낼 답도 1로 초기화

 

 

 

3-2 queue 동작 (추가된 요소를 확인)

 

 

 

queue가 비어있지 않으면 (움직일 수 있다면)

queue에 들어 있는 건 (전 위치에서 움직일 수 있는)현재 위치 이다.

 

예를 들어 임의로 정하자면 상, 하, 좌 or 상 하  등등..

 

queue서 꺼냈는데, 그 값이 마지막에 도달했다면 이때까지 움직인 거리인 answer를 return해줌 !

 

 

 

3-3 실제 추가되는 요소들

 

 

먼저 movement에 저장된 움직임들을 더해준다.

 

한 방향씩 움직일 수 잇는 건 현재 위치 + 다음 방향의 움직임들

 

 

(1,1) 에서 아래로 움직인다면,  tox = 2, toY = 1이라   (2,1)

 

그 움직인 곳을 검사해주면 된다.

 

 

조건은 내가 움직일 곳이

 

• 방문한 적이 없어야 한다 (isVisited배열로 확인)
• maps에서 벽으로 표시되어 있지 않아야 한다. (maps 의 값이 1)
• 0보다 크거나 같고, 배열의 크기보다 작아야 한다. (벗어날 범위 확인)
•  

 

 

조건에 부합한다면 queue에 움직인 곳으로 표시되어 넣어주고,

움직인 거리인 answer를 1추가한 다음 while문에서 끝인지 다시 확인 반복~

 

 

만약 while 문을 다 돌고 나올 경우엔 도착할 수 없기에 -1 return

 

 

 

3. 마무리

 

성공 !

 

 

일단 끝까지 돌아야 하는 문제들만 풀어가지고, dfs와 bfs는 취향의 차이인 줄 알았으나

 

상황에 따라 더 유리한 알고리즘은 분명히 있었다,, 모르고 dfs로 구현하다 알아차렸음 ㅠㅠ

 

잘 구분하자.. 

 

처음 구현해봐서 이해하면서 찾아 구현하느라 아직 서툴다 ㅠㅠ

 

 

 

멍청하게 먼저 toX와 toY가 음수가 아니게 검사하고 배열의 index로 사용해야 하는데 !

 

위처럼 반대로 해서 ArrayIndexOutOfBoundsException를 만났다..

 

이 얼마나 단순한 걸 자꾸 틀리는가..

 

잘하자