[프로그래머스,Java] Level2: 게임 맵 최단거리

 

문제분석

 

따로 어려운 규칙도없고, 단순 길찾기문제이다.

 

길찾기 문제를 처음접하고 풀어보는 사람이라면 연습하기에 딱 좋은 기출문제입니다.

 

 

길찾기 문제를 풀기위해선 완전탐색을 구현하셔야합니다. 

 

모든 4방향길을 완전탐색해서 최적의 길을 찾아야하니깐요.

 

완전탐색을 구현하는 2가지 방법이 존재하죠

 

BFS, DFS방법이있습니다.  DFS는 Stack,재귀함수  BFS는 Queue 처럼 구현한다고 생각하시면됩니다.

 

DFS VS BFS

 

DFS는 깊이 우선 탐색입니다.  쉽게말하면, 한 우물을 깊게 먼저파는 탐색방법입니다.

 

BFS는 너비 우선 탐색입니다.  이건 반대로, 얇고 넓게 파는 탐색방법입니다.

 

저희는 최소의 길을 찾아야하는데,  DFS, BFS중 무엇을 사용해야 효율적일까요?

 

당연히 BFS입니다.

 

얇게 넓게파다가, 가장 얇은층 (최소거리로 목적지도착)하는걸 찾을수있으니깐요.

 

한 우물만 먼저 파는 DFS로 구현하면  최적의 거리를 찾기까지 많은 시간(쓸모없는탐색이 많아짐)이 걸립니다.

 

BFS는 Queue를 사용해서 구현한다고 하였으니 구현합시다.

 

길을 찾을때 탐색방향은 4가지, 위 아래 우, 왼 을 구현하고 목적지를 만날때까지 반복시킵니다.

 

벽을 부딪히거나, 범위를 넘어가는경우는 잊지말고 제외합시다.

 

BFS를통해 제일 일찍찾은 목적지가 최적의 거리입니다. 고민하지말고 Return합시다.

 

거리를 세는건 여러가지 방법이 있다만, 저는 횟수를세어주는 count맵을 생성해, 

지나갈때마다 count를 남겨놓는 방식을 사용했습니다.

 

만약, 탐색이완료되도 목적지를 찾지못하면 return -1를 반환하시면 됩니다.

문제풀이

import java.util.*;
class Solution {
    public int solution(int[][] maps) {
        int answer = 0;
        int[][] move ={{0,1},{0,-1},{1,0},{-1,0}};
        Queue<Position> que =new LinkedList();
        int[][] count =new int[maps.length][maps[0].length];
        
        que.add(new Position(0,0));
        count[0][0]=1;
        
        while(!que.isEmpty()){
            Position cur =que.poll();
            int curcount = count[cur.y][cur.x];
            for(int i=0;i<4;i++){
            Position p = new Position(cur.x+move[i][0],cur.y+move[i][1]);
            //맵밖으로 나갈때
            if(p.x<0||p.y<0||p.x==maps[0].length||p.y==maps.length){
                continue;
            }
            //벽에 부딪힐때
            if(maps[p.y][p.x]==0){
                continue;
            }
            count[p.y][p.x]=curcount+1;
            //이미 지난길은 벽으로 만들어버리기
            maps[p.y][p.x]=0;
            que.add(p);
            }
        }
        answer=count[maps.length-1][maps[0].length-1];
        if(answer==0){
            return -1;
        }
        return answer;
    }
}
 
class Position {
    int x,y;
    
    public Position(int x, int y){
        this.x=x;
        this.y=y;
    }
}