프로그래머스 - 게임 맵 최단 거리

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

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

• 그래프 탐색 문제이다.
• DFS로 시도하였으나 시간 초과 및 반례가 있어 BFS로 변경하여 풀었다.
• 입력 형태가 맵 + BFS 요구 여서 인접 노드를 어떻게 탐색해야 하나 궁금했다
  • move라는 배열로 이동 가능한 범주를 주어 인접 노드 탐색을 찾는 것으로 해결했다.

import java.util.LinkedList;
import java.util.Queue;

class Solution {
        public int solution(int[][] maps) {
            int answer = -1;
            int goldR = maps.length - 1;
            int goldC = maps[0].length - 1;

            int[][] move = new int[][]{
                    {1, 0},
                    {-1, 0},
                    {0, 1},
                    {0, -1},
            };
            boolean[][] visited = new boolean[maps.length][maps[0].length];

            Queue<State> queue = new LinkedList<>();
            queue.offer(new State(0, 0, 1));
            while (!queue.isEmpty()) {
                State currentNode = queue.poll();
                if (visited[currentNode.r][currentNode.c] == true) continue;
                visited[currentNode.r][currentNode.c] = true;

                if(currentNode.r == goldR && currentNode.c == goldC) {
                    answer = currentNode.depth;
                    break;
                }

                for (int i = 0; i < 4; i++) {
                    int nextR = currentNode.r + move[i][0];
                    int nextC = currentNode.c + move[i][1];
                    if (nextR >= maps.length || nextR < 0) continue;
                    if (nextC >= maps[0].length || nextC < 0) continue;
                    if (maps[nextR][nextC] == 1) {
                        queue.offer(new State(nextR, nextC, currentNode.depth + 1));
                    }
                }
            }

            return answer;
        }
    }

 class State {
        public int r;
        public int c;
        public int depth; // 이동거리

        public State(int r, int c, int depth) {
            this.r = r;
            this.c = c;
            this.depth = depth;
        }
    }