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

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

프로그래머스

 

 

 

⭐️ 중요 포인트

1. 제한 조건(벽, (n, m)이 목표)을 잘 따르고

2. isVisited[][]로 기존에 방문한 곳을 방문하지 않으며

3. BFS를 돌면 간단하게 해결할 수 있는 문제.

 

import java.util.*;

class Solution {
    
    static class Pos {
        int x;
        int y;
        int cnt;
        
        Pos(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
    
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {-1, 0, 1, 0};
    
    static int[][] sMaps;
    static boolean[][] isVisited;
    static int answer;

    static void init(int[][] maps) {
        sMaps = maps;
        isVisited = new boolean[sMaps.length][sMaps[0].length];
        answer = 0;
        
    }
    
    static boolean isInRange(int x, int y) {
        if (0 <= y && y < sMaps.length && 0 <= x && x < sMaps[0].length ) {
            return true;
        }
        
        return false;
    }
    
    static int bfs() {
        Deque<Pos> q = new ArrayDeque<>();
        q.add(new Pos(0, 0, 1));
        isVisited[0][0] = true;
        
        while (!q.isEmpty()) {
            Pos curPos = q.pop();
            int curX = curPos.x;
            int curY = curPos.y;
            int curCnt = curPos.cnt;
            
            if (curY == sMaps.length - 1 && curX == sMaps[0].length - 1) {
                return curCnt;
            }
            
            for (int i = 0; i < 4; i++) {
                int nextX = curX + dx[i];
                int nextY = curY + dy[i];
                
                if (isInRange(nextX, nextY) && sMaps[nextY][nextX] == 1 && !isVisited[nextY][nextX]) {
                    q.add(new Pos(nextX, nextY, curCnt + 1));
                    isVisited[nextY][nextX] = true;
                }
            }
            
        }
        return -1;
    }
    
    public int solution(int[][] maps) {
        init(maps);
        
        answer = bfs();
        
        return answer;
    }
}