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

🔺 문제

프로그래머스

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
class Solution {
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};
    
    static int[][] maps, dist;
    static boolean[][] visited;
    static int answer = 0;
    
    static int row, col;
    
    public int solution(int[][] maps) {
        this.maps = maps;
        
        row = maps.length;
        col = maps[0].length;
        
        dist = new int[row + 1][col + 1];
        visited = new boolean[row + 1][col + 1];
        
        bfs(0, 0);    // (0,0) 에서 BFS 한 번만 수행
 
        return answer;
    }
    
    private static void bfs(int a, int b) {
        visited[a][b] = true;
        
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {a, b});
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            
            for(int d = 0 ; d < 4 ; d++) {
                int x = now[0] + dx[d];
                int y = now[1] + dy[d];
                
                if(x < 0 || y < 0 || x >= row || y >= col) continue;
                if(visited[x][y] || maps[x][y] == 0) continue;
                
                if(!visited[x][y] && maps[x][y] == 1) {
                    visited[x][y] = true;
                    dist[x][y] = dist[now[0]][now[1]] + 1;
                    q.add(new int[] {x, y});
                }
            }
        }
        
        answer = (dist[row - 1][col - 1] == 0) ? - 1 : (dist[row - 1][col - 1] + 1);
    }
}

✅ 해결 아이디어
✔ BFS
: 최단 거리 구하는 거니까 BFS로 풀었다.
(0,0)에서 상하좌우 탐색하면서, 이동 가능한 칸 발견 시 큐에 추가하고, 거리 배열을 갱신하며 이동한다.

마지막 칸의 값이 0이면 마지막 칸에 도달하지 못 한 것이므로 -1을 출력하고,
그게 아니라면 거리 배열의 마지막 칸 값을 출력한다.

 

 

---

🔺 다른 풀이들

- 나처럼 방문 배열과 거리 배열을 따로 둘 필요 없이, 아래 코드처럼 방문 겸 거리 배열 하나만 작성해서 해도 된다!

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

 

 

- 깔끔하시다... 상하좌우도 향상형 for문 쓰심!

큐에 파라미터로 시작 위치와 거리를 함께 가져가시면서 거리를 갱신하심

import java.util.*;

class Solution {
    public int solution(int[][] maps) {
        int rows = maps.length;
        int cols = maps[0].length;

        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 상하좌우

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0, 1}); // 시작 위치와 거리

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int row = current[0];
            int col = current[1];
            int distance = current[2];

            if (row == rows - 1 && col == cols - 1) {
                return distance; // 목적지에 도달한 경우 최단거리 반환
            }

            for (int[] dir : directions) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];

                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && maps[newRow][newCol] == 1) {
                    maps[newRow][newCol] = 0; // 방문한 위치는 재방문하지 않도록 표시
                    queue.offer(new int[]{newRow, newCol, distance + 1});
                }
            }
        }

        return -1; // 목적지에 도달하지 못한 경우
    }
}

---

💬 느낀 점

이런 문제만 나오면 좋겠구나,,,,하하하ㅏ

 

 

1회독	2회독	3회독	4회독	5회독
V