99클럽 코테 스터디 35일차 TIL - [프로그래머스] 게임 맵 최단거리 (Java)

📌 오늘의 학습 키워드

[프로그래머스] 타겟 넘버 (Java)
https://school.programmers.co.kr/learn/courses/30/lessons/43165

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : 게임 맵의 상태 maps
출력 : 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값. 단, 상대 팀 진영에 도착할 수 없다면 -1 리턴

가능한 시간복잡도

O(n)

알고리즘 선택

bfs

📌 코드 설계하기

1. 미로의 크기를 파악하고, BFS 탐색을 위한 큐(Queue)를 생성한다.
2. 시작점(0,0)에서 출발하며, 이 위치를 큐에 추가하고 방문 기록을 남긴다.
3. 큐가 빌 때까지 반복하며, 현재 위치를 꺼내어 4개의 방향(상하좌우)으로 이동 가능한지 검사한다.
4. 미로의 범위 내에서 이동 가능하고, 아직 방문하지 않은 칸이면 큐에 추가하고 방문으로 기록한다.
5. 목표 지점(미로의 끝)에 도달하면 현재까지 이동한 거리를 반환한다. 큐가 비어도 목표에 도달하지 못하면 -1을 반환한다.

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

어떻게 해결했는지

무엇을 새롭게 알았는지

Queue에서 add는 요소를 추가할 수 없을 때 예외를 던지는 반면, offer는 예외를 던지지 않고 단순히 false를 반환함

내일 학습할 것은 무엇인지

구현

📌 정답 코드

import java.util.*;

class Solution {
 private int[] dx = new int[]{-1, 1, 0, 0};
    private int[] dy = new int[]{0, 0, -1, 1};
    private int n;
    private int m;

    public int solution(int[][] maze) {
        n = maze.length;
        m = maze[0].length;
        // BFS 로직을 활용하는데,
        // 다음에 접근할 수 있는 칸을 maze 의 가로 세로 크기 이내의 인접한 칸
        // 을 기준으로 판단

        // int[]를 담는 Queue, {x, y, 여태까지 이동거리}
        Queue<int[]> visitNext = new LinkedList<>();
        boolean[][] visited = new boolean[n][m];
        visitNext.offer(new int[]{0, 0, 1});
        int answer = -1;
        // BFS 시작
        // Queue가 비어있지 않은 동안
        while (!visitNext.isEmpty()) {
            // 다음에 갈곳을 Queue에서 꺼낸다.
            int[] next = visitNext.poll();
            int nowX = next[0];
            int nowY = next[1];
            int steps = next[2];
            // 현재 칸이 n, m 이라면,
            if (nowX == n - 1 && nowY == m - 1){
                answer = steps;
                break;
            }

            // 4개의 방향을 확인한다.
            for (int i = 0; i < 4; i++) {
                int nextX = nowX + dx[i];
                int nextY = nowY + dy[i];
                if (
                        // 1. 미로의 범위를 벗어나진 않는지
                        checkBounds(nextX, nextY) &&
                        // 2. 미로에서 진행 가능한 칸인지 (0 또는 3)
                        maze[nextX][nextY] == 1 &&
                        // 3. 아직 방문한적 없는지
                        !visited[nextX][nextY]
                ) {
                    // 큐에 방문 대상으로 기록
                    visitNext.offer(new int[]{nextX, nextY, steps + 1});
                    // 효율성 검사 통과를 위해 방문 전에 기록한다.
                    visited[nextX][nextY] = true;
                }
            }
        }
        return answer;
    }

    // 미로의 범위 내에 있는지 검사하는 메소드
    private boolean checkBounds(int x, int y) {
        return -1 < x && x < n && -1 < y && y < m;
    }

}