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

https://programmers.co.kr/learn/courses/30/lessons/1844?language=java 

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

 

---

 

[풀이]

 

 제목에도 나와있고 문제에도 나와있듯이 주어진 맵에서 최단거리를 구하는 문제이다. 그렇기에 BFS로 문제를 풀려고 시도했다. 0은 벽이 있는 자리, 1은 벽이 없는 자리인데 전형적인 BFS문제이기에 BFS에 대한 입문 문제로 풀기 좋은 문제였다고 생각한다. 마지막에, 상대 팀 진영에 도착을 하지 못한다면 -1을 반환하는 부분만 조건문을 작성하면 그외 특별한 부분은 없다!

 

 혹시나, BFS에 대한 개념이 부족하다고 생각하시는 분이 있다면, 나동빈님의 BFS, DFS 유튜브 강의를 보시면 좋을 것 같다. 물론 파이썬으로 강의를 하시지만 개념을 충분히 배울 수 있을 것이다.

 

---

 

[코드]

 

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int[][] dp;
    
    static class Node {
    int x;
    int y;

        Node(int _x, int _y) {
            this.x = _x;
            this.y = _y;
        }
    }

    public int solution(int[][] maps) {
        int row = maps.length;
        int column = maps[0].length;
        visited = new boolean[row][column];
        dp = new int[row][column];
        bfs(0, 0, maps);

        if (dp[row - 1][column - 1] > 1) {
            return dp[row - 1][column - 1];
        } else {
            return -1;
        }
    }

    static void bfs(int x, int y, int[][] maps) {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(x, y));
        visited[x][y] = true;
        dp[x][y] = 1;

        while (!queue.isEmpty()) {
            Node now = queue.poll();

            for (int i = 0; i < 4; i++) {
                int now_x = now.x + dx[i];
                int now_y = now.y + dy[i];

                if (now_x < 0 || now_x >= maps.length || now_y < 0 | now_y >= maps[0].length) {
                    continue;
                }

                if (maps[now_x][now_y] == 0) {
                    continue;
                }

                if (!visited[now_x][now_y]) {
                    visited[now_x][now_y] = true;
                    dp[now_x][now_y] = dp[now.x][now.y] + 1;
                    queue.offer(new Node(now_x, now_y));
                }
            }
        }
    }
}