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

문제 링크

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

문제 풀이

상하좌우 방향을 살펴야 하므로 이를 배열로 만들어서 처리

    static int [] diry = {-1,0,1,0};//상 우 하 좌
    static int [] dirx = {0,1,0,-1};

x,y 좌표를 활용할 것이기 때문에 x,y 좌표를 가질 Node 라는 클래스를 만든다.

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

이 Node를 자료형으로 가지는 Queue를 선언한다.

Queue<Node> queue = new LinkedList<>();

조건에 맞는 칸들을 queue에 담아 주게 된다.

초기값을 queue에 담아준다.

queue.add(new Node(y, x));

반복문은 queue에 값이 없을때 까지 반복되며
queue에 값이 없다는 뜻은 더이상 탐색할 곳이 없다는 뜻이다.

while (!queue.isEmpty()) 

queue에 제일 앞에 있는 값을 뽑아서 처리한다.

Node now = queue.poll();

현재 값에 대해서 상하좌우에 대해서 반복문을 돌린다. (상하좌우이기 때문에 4번만 돌리면된다.)

for (int i = 0; i < 4; i++) { ...}

현재 값에다가 상,하,좌,우를 더한 된 값이
now_y, now_x 이다.

 int now_y = now.y + diry[i];
 int now_x = now.x + dirx[i];

상,하,좌,우 이동한 값이 map을 벗어나는지 먼저 체크를 하고
벗어나지 않는다면 상,하,좌,우 이동한 칸이 한번도 이동한적이 없는 칸인지 체크
이동한적이 없는 칸이라면 queue에 그 칸에 대한 정보를 추가하고
이동할 칸에다가 현재 칸의 이동횟수에 +1을 해준다.

map의 값은 이동거리의 누적횟수라고 생각하면 된다.

if (0 <= now_y && now_y < n && 0 <= now_x && now_x < m) {
                    if (map[now_y][now_x] != 0 && !chk[now_y][now_x]) {
                        queue.add(new Node(now_y, now_x));
                        chk[now_y][now_x] = true;
                        map[now_y][now_x] = map[now.y][now.x] + 1;
                    }
                }

코드

import java.util.*;

class Solution {
    
    static boolean [][] chk;
    static int [] diry = {-1,0,1,0};//상 우 하 좌
    static int [] dirx = {0,1,0,-1};
    static int [][] map;
    static int n;
    static int m;
    
    public class Node{
        int x;
        int y;
        
        public Node(int y, int x){
            this.y=y;
            this.x=x;
        }
    }
    
    public int solution(int[][] maps) {
        int answer = 0;
        n = maps.length;
        m = maps[0].length;
        chk = new boolean[n][m];
        
        chk[0][0] = true;
        bfs(0,0);
        
        answer = map[n-1][m-1];
        return answer>1 ? map[n-1][m-1] : -1 ;
    }
    
    public  void bfs(int y, int x) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(y, x));

        while (!queue.isEmpty()) {
            Node now = queue.poll();
            for (int i = 0; i < 4; i++) {
                int now_y = now.y + diry[i];
                int now_x = now.x + dirx[i];
                if (0 <= now_y && now_y < n && 0 <= now_x && now_x < m) {
                    if (map[now_y][now_x] != 0 && !chk[now_y][now_x]) {
                        queue.add(new Node(now_y, now_x));
                        chk[now_y][now_x] = true;
                        map[now_y][now_x] = map[now.y][now.x] + 1;
                    }
                }
            }
        }

    }
}