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

풀이 방식

1. 초기화

• 초기 정답 값 = -1 (답이 없을 경우 -1)
• 목표 지점의 열 endRow, 목표 지점의 행 endCol
• 동서남북 방향 directions
• 너비우선탐색을 위해 찾아갈 목록을 저장할 큐 queue
• 시작 지점 큐에 넣기

2. 너비우선탐색 while문

• 변수 초기화:
  찾아갈 목록에서 제일 상단 지점을 현재 칸 current로 지정
  현재 칸의 열 row와 행 col 저장
  첫 지점부터 현재까지의 거리 distance 저장
• 종료 조건:
  목표 지점까지 갔다면 정답에 거리를 저장하고 종료
  예외) 찾아갈 목록이 비어버리면 자동 종료
• 점화식:
  for-each문을 통해 4방향 탐색
  가려는 곳이 범위를 벗어나지 않으면서 길이 맞다면 거리+1 한 후 찾아갈 목록에 추가
  간 지점은 벽 세우기

포인트

queue 배열

배열을 요소로 가지는 queue
각 요소가 int 배열로 이루어짐
int 배열의 요소는 {row, col, distance}로 이루어짐

	LinkedList<int[]> queue = new LinkedList<>();
    queue.offer(new int[]{0, 0, 1});

구현

import java.util.LinkedList;

public class NUM1844 {
    public static void main(String[] args) {
        int[][] maps = {{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}};
        System.out.println(solution(maps));
    }
    public static int solution(int[][] maps) {
        int answer = 0;
        answer = -1;

        int endRow = maps.length - 1;
        int endCol = maps[0].length - 1;
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        LinkedList<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0, 1});

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            if (current[0] == endRow && current[1] == endCol) {
                answer = current[2];
                break;
            }

            for (int[] dir : directions) {
                int newRow = current[0] + dir[0];
                int newCol = current[1] + dir[1];
                if (newRow >= 0 && newRow <= endRow && newCol >= 0 && newCol <= endCol && maps[newRow][newCol] == 1) {
                    queue.offer(new int[]{newRow, newCol, current[2] + 1});
                    maps[newRow][newCol] = 0;
                }
            }
        }

        return answer;
    }
}

---

*다른 분들의 코드를 참고하여 작성했습니다