프로그래머스 - 게임 맵 최단거리 문제 (자바)

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

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

일반적인 DFS/BFS 문제로 시작지점에서 도착지점까지의 최단 거릴를 구하면됩니다.

개인적으로 이런 MAP에서 이동 문제는 BFS를 선호하기 때문에 BFS을 사용하여 해결하였습니다.

 

주의점

주의점이라고 하기도 뭐하지만 이동이 불가능하면 -1을 리턴해야하는데 Arrays.fill을 통해서 -1을 채워 넣지않으면 retrun 할때 조건문이나 삼항식을 이용해서 0 이면 -1 이런식으로 해야합니다. 둘다 해봤을때 시간차이는 유의미하지않았어서 Arrays.fill을 사용했지만 배열의 크기가 커진다면 조건문이 좀더 좋을거라고 생각합니다,(삼항식은 가독성이....)

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

// 프로그래머스 게임 맵 최단거리
class Dot {
    int x;
    int y;

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

class Solution {

    static int[][] dp;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public int solution(int[][] maps) {
        int row = maps.length;
        int column = maps[0].length;
        visited = new boolean[row][column];
        dp = new int[row][column];
        for (int[] ints : dp) {
            Arrays.fill(ints, -1);
        }

        bfs(0,0, maps);

        return dp[row - 1][column - 1];
    }

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

        while (!q.isEmpty()) {
            Dot now = q.poll();

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

                // 범위를 벗어 나는 경우
                if(tx < 0 || tx >= maps.length || ty < 0 || ty >= maps[0].length) continue;

                // 벽인 경우
                if(maps[tx][ty] == 0) continue;

                // 미방문인 경우 방문 처리 및 dp 값 셋팅
                if(!visited[tx][ty]) {
                    visited[tx][ty] = true;
                    dp[tx][ty] = dp[now.x][now.y] + 1;
                    q.offer(new Dot(tx, ty));
                }
            }
        }
    }
}