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

프로그래머스 

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

# 난이도 : LV.2

---

문제내용

---

제한사항

---

입출력 예

---

풀이방법

좌표를 저장할 Point 클래스를 생성한 뒤 BFS메서드와 Queue를 통해 문제를 해결하였습니다 !

상하좌우 탐색이 이루어져야 하기 때문에 dx, dy 변수를 생성하여 현재의 위치에서 상하좌우 탐색을 진행하였습니다.

중요한 포인트는 기존에 탐색이 이루어진 부분은 1로 초기화를 해줘야 된다는 점 ! (무한루프가 돌 수 있습니당)

탐색은 최단거리로 진행되어야 하며, 도착지점에 값이 제일 빨리 도착하는 수로 초기화되고 최단거리가 아닌 경우의 수가 도착지점에 도착할 경우 탐색이 이루어진 부분은 1로 초기화를 하였기 때문에 도착지점의 값은 최단거리의 값에서 변경될 수 없습니다.

백준 문제만 풀다 보니 헷갈렸던 점은 움직일 수 있는 배열의 원소가 0이 아니라 1이였다는 점.....조심하셔요 !

---

코드

import java.util.*;

class Point{
    public int x, y;
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}

class Solution {
    static int[][] visit;
    static int[][] board;
    static int n, m;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    public int solution(int[][] maps) {
        n = maps.length;
        m = maps[0].length;
        visit = new int[n][m];
        BFS(0, 0, maps);
        if(visit[n - 1][m- 1] == 0) return -1;
        else return visit[n- 1][m- 1];
    }
    
    public static void BFS(int x, int y, int[][] maps){
        Queue<Point> Q = new LinkedList<>();
        Q.offer(new Point(x, y));
        visit[x][y] = 1;
        while(!Q.isEmpty()){
            Point point = Q.poll();
            for(int i = 0; i < 4; i++){
                int nx = point.x + dx[i];
                int ny = point.y + dy[i];
                if(nx >= 0 && nx < n && ny >= 0 && ny < m && maps[nx][ny] == 1){
                    maps[nx][ny] = 0;
                    Q.offer(new Point(nx, ny));
                    visit[nx][ny] = visit[point.x][point.y] + 1;
                }
            }
        }
        
    }
}