[프로그래머스] 게임 맵 최단거리 (JAVA)

문제 출처 - Programmers

문제는 여기

코딩테스트 연습 - 게임 맵 최단거리

---

[풀이]

1. 4방 탐색을 위한 dx, dy 배열을 만들어준다.

2. 방문체크를 위한 배열을 만들어준다.

3. 시작위치를 1로 만들어 방문 체크를 해준다.

4. bfs 탐색을 한다.

5. 범위를 벗어나는지, 방문 했는지, 갈 수 있는 곳인지를 체크한다.

6. 체크해서 문제가 없다면 해당 위치까지 방문한 수 + 1을 넣어준다.

7. bfs를 추가적으로 탐색한다.

8. 결과를 answer에 넣는다.

9. answer이 0이라면 도착할 수 없는 곳이므로 -1로 넣어준다.

10. 결과를 출력한다.

[접근]

1. BFS를 사용해서 맵을 탐색하면 되겠다고 생각하였다.

[코드]

import java.util.*;

class Solution {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {-1, 1, 0, 0};
    
    public int solution(int[][] maps) {
        int answer = 0;
        int[][] visited = new int[maps.length][maps[0].length];
        
        visited[0][0] = 1; // 시작 위치 방문체크
        
        // bfs 탐색
        bfs(maps, visited);
        // 도착지 값을 넣어주기
        answer = visited[maps.length - 1][maps[0].length - 1];
        
        // 갈 수 없다면 -1리턴
        if (answer == 0) {
            answer = -1;
        }
        
        return answer;
    }
    
    public void bfs(int[][] maps, int[][] visited) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0});
        
        while (!q.isEmpty()) {
            int[] now = q.poll();
            int x = now[0];
            int y = now[1];
            
            // 4방탐색
            for (int i = 0; i < 4; i++) {
                // 이동했을 때 위치
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                // 범위 벗어나는지 체크
                // 방문했는지 체크
                // 갈 수 있는지 체크
                if (nx >= 0 && nx < maps.length && ny >= 0 && ny < maps[0].length
                    && visited[nx][ny] == 0 && maps[nx][ny] == 1) {
                    // 방문했다고 체크해주기
                    visited[nx][ny] = visited[x][y] + 1;
                    // 큐에 넣기
                    q.add(new int[]{nx, ny});
                }
            }   
        }
    }
}