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

📝 문제

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

프로그래머스

[설명]

n x m 크기의 게임 맵 시작 지점에서, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 최소 칸의 개수 구하기

단, 상대 팀 진영에 도착할 수 없을 때는 -1 리턴

 

[접근 방법]

BFS(너비 우선 탐색) 활용

 

[주의 사항]

BFS 활용법 외우면 풀기 수월하다.

방문처리는 큐에 넣을 때 꼭 같이 해줘야한다.

참고 : https://school.programmers.co.kr/questions/38232

 

🔑 풀이

import java.util.ArrayDeque;
import java.util.Arrays;

    class Solution {

        private static final int[] rx = {0, 0, 1, -1};
        private static final int[] ry = {1, -1, 0, 0};

        private static class Node {
            int r, c;

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

        }

        public int solution(int[][] maps) {
            int answer = 0;

            int N = maps.length;
            int M = maps[0].length;

            ArrayDeque<Node> queue = new ArrayDeque<>();
            boolean[][] visited = new boolean[N][M]; // 정점에 대한 방문처리 배열
            int[][] dist = new int[N][M]; // 최단거리 배열

            queue.addLast(new Node(0, 0));
            visited[0][0] = true; // 방문
            dist[0][0] = 1;

            while (!queue.isEmpty()) {
                Node now = queue.pollFirst(); // 현재 위치한 정점

                for (int i = 0; i < 4; i++) { // 상하좌우 탐색
                    int nr = now.r + rx[i];
                    int nc = now.c + ry[i];

                    if (nr < 0 || nc < 0 || nr >= N || nc >= M) {
                        continue; // map 밖으로 나가는 경우, 예외처리
                    }

                    if (maps[nr][nc] == 0) // 갈 수 없는 곳 (벽)
                        continue;

                    if (!visited[nr][nc]) {
                        visited[nr][nc] = true; // 방문처리 (중요!)
                        queue.addLast(new Node(nr, nc));
                        dist[nr][nc] = dist[now.r][now.c] + 1; // 다음 정점 최단거리 = 현재 정점 최단거리+1
                    }
                }
            }

            return dist[N - 1][M - 1] == 0 ? -1 : dist[N - 1][M - 1];
        }

    }

 

📌 TIL

BFS 개념 및 활용법

https://kimjunhyun.tistory.com/66