LV2 게임 맵 최단거리 (Java)

 

---

 

문제

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

프로그래머스

풀이

완전 기초 bfs이다. 

 

거리를 잴 distance와 방문 여부를 따질 visited를 선언한 후에

 

좌표 [0, 0] 부터bfs를 수행한다.

 

범위검사, 방문여부, 벽 존재 여부를 따지면서 bfs를 수행하고

 

목표하던 곳이 방문되지 않았다면 -1, 그게 아니라면 distance 값을 리턴해주면 된다.

 

코드

import java.util.*;

class Solution {
    
    public int[] dx = {0, 0, 1, -1};
    public int[] dy = {1, -1, 0 ,0};
    
    public int solution(int[][] maps) {
        
        int n = maps.length;
        int m = maps[0].length;
        int[][] distance = new int[n][m];
        boolean[][] visited = new boolean[n][m];

        Queue<ArrayList<Integer>> q = new LinkedList<>();
        q.add(new ArrayList<Integer>(Arrays.asList(0, 0)));
        distance[0][0] = 1;
        visited[0][0] = true;
        
        while(q.peek() != null){
            int x = q.peek().get(0);
            int y = q.peek().get(1);
            q.poll();
            
            for(int i=0; i<4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if(nx >= 0 && nx < n && ny >= 0 && ny < m 
                   && visited[nx][ny] == false && maps[nx][ny] == 1){
                    q.add(new ArrayList<Integer>(Arrays.asList(nx, ny)));
                    visited[nx][ny] = true;
                    distance[nx][ny] = distance[x][y] + 1;
                }
            }
        }
                
        if(visited[n-1][m-1] == false) return -1;
        
        return distance[n-1][m-1];
    }
}

 

후기

 

Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{0, 0})

 

기본 배열 다루는게 헷갈려 list를 사용했으나, 기본배열은 위처럼 사용하면 된다.