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

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

programmers.co.kr/learn/courses/30/lessons/1844

코딩테스트 연습 - 게임 맵 최단거리

풀이

프로그래머스 레벨4 문제 임에도 불구하고 BFS를 사용하면 금방 풀리는 문제이다.

 

BFS를 사용하는 이유는 최단경로를 탐색하기 때문이다. 

현재까지의 cost를 저장해 주기 위해 Node class를 만들어 주었다.

BFS의 반환 타입을 int형으로 해주어 x, y가 도착 노드에 도착했다면 그 때의 cost를, q를 다 돌았는데도 x, y에 도착하지 못했다면 막혀있다는 의미이므로 -1을 반환하도록 해주었다.

 

코드

import java.util.*;
 
class Solution {
    
    int[] dx = {0, 1, 0, -1};
    int[] dy = {-1, 0, 1, 0};
    boolean[][] visited;
    int n, m;
    
    public int solution(int[][] maps) {
        n = maps.length;
        m = maps[0].length;
        
        visited = new boolean[n][m];
        return bfs(0, 0, maps);
    }
    
    public int bfs(int x, int y, int[][] maps) {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x, y, 1));
        visited[x][y] = true;
        
        while(!q.isEmpty()) {
            Node node = q.poll();
            if(node.x == n - 1 && node.y == m - 1) return node.cost;
            
            for(int i = 0; i < 4; i++) {
                int nx = node.x + dx[i];
                int ny = node.y + dy[i];
                if(nx >= 0 && ny >= 0 && nx < n && ny < m) {
                    if(maps[nx][ny] == 1 && !visited[nx][ny]) {
                        visited[nx][ny] = true;
                        q.offer(new Node(nx, ny, node.cost + 1));
                    }
                }
            }
        }
        return -1;
    }
    
    public class Node {
        int x;
        int y;
        int cost;
        
        public Node(int x, int y, int cost) {
            this.x = x;
            this.y = y;
            this.cost = cost;
        }
    }
}