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

• 문제 링크 : 게임 맵 최단거리

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

 

정답(Solution)

import java.util.*;

class Solution {

    private class Position {
        int x, y;

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

    public int solution(int[][] maps) {
        int height = maps.length;
        int width = maps[0].length;

        Queue<Position> queue = new LinkedList<>();
        int[][] count = new int[height][width];
        boolean[][] v = new boolean[height][width];

        queue.offer(new Position(0, 0));
        count[0][0] = 1;
        v[0][0] = true;

        while(!queue.isEmpty()){
            Position current = queue.poll();

            int nowCount = count[current.x][current.y];

            int[][] move = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
            for(int i=0; i<move.length; i++){
                Position moved = new Position(current.x + move[i][0], current.y + move[i][1]);
                if(moved.x < 0 || moved.x >= height || moved.y < 0 || moved.y >= width) continue;
                if(v[moved.x][moved.y]) continue;
                if(maps[moved.x][moved.y] == 0) continue;

                count[moved.x][moved.y] = nowCount + 1;
                v[moved.x][moved.y] = true;
                queue.offer(moved);
            }
        }

        int answer = count[height -1][width -1];
        if(answer == 0) return -1;

        return answer;
    }
}

 

분석

• bfs를 이용해서 길을 찾는 문제
• bfs는 기본적으로 Queue를 사용한다.
• dfs보다 현재에서 가장 가까운 방향으로 탐색하기 때문에 빠르게 찾을 수 있다.
• answer이 초기값 0을 가지고 있는 경우에는 해당 위치에 도달하지 못 했다는 의미이다.