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

 

 

문제 파악

-시작점(1,1)에서 도착점(n,m)까지 최단 거리를 구하기

• maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
  • n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
• maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
• 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

접근 방법

💡 -배열은 (0,0)부터인데 지문은 (1,1)이기 때문에 일관성있게 0based index유지해야함

-(첫트) DFS : Integer.MAX_VALUE로 최대한 큰 값 넣어놓고 최솟값 할당해나가기

-(2트) BFS : 완전 탐색 → 큐를 활용하기

 

코드 구현-BFS

import java.util.*;
class Solution {
    public int solution(int[][] maps) {
        int n=maps.length;
        int m=maps[0].length;
        Queue<int[]> que = new ArrayDeque<>();
        que.offer(new int[]{0,0,1});//(1,1) 시작점
        
        while(!que.isEmpty()){
            int[] node=que.poll();
            int row=node[0];
            int col=node[1];
            int lev=node[2];
            if(row>=0 && row<n && col>=0 && col<m && maps[row][col]==1){
                if(row==n-1&&col==m-1){
                    return lev;
                }
                maps[row][col] = 0;
                que.offer(new int[]{row-1,col,lev+1});
                que.offer(new int[]{row+1,col,lev+1});
                que.offer(new int[]{row,col-1,lev+1});
                que.offer(new int[]{row,col+1,lev+1});
            }
        }
        return -1;
    }
}

```java
import java.util.*;
class Solution {
    public int solution(int[][] maps) {
        int n=maps.length;
        int m=maps[0].length;
        
        Queue<int[]> que = new ArrayDeque<>();
        boolean[][] visited=new boolean[n+1][m+1];
        que.offer(new int[]{0,0,1});
        visited[0][0]=true;
        int[] toX={-1,1,0,0};
        int[] toY={0,0,-1,1};
        while(!que.isEmpty()){
            int[] node = que.poll();
            int cx = node[0];
            int cy = node[1];
            int cl = node[2];
            if(cx==n-1 && cy==m-1){
                return cl;
            }
            for(int k=0;k<4;k++){
                int ax=cx+toX[k];
                int ay=cy+toY[k];
                if(ax>=0 && ax<n && ay>=0 && ay<m && maps[ax][ay]==1){
                    if(!visited[ax][ay]){
                        visited[ax][ay]=true;
                        que.offer(new int[]{ax,ay,cl+1});
                    }
                }     
            }
        }
        return -1;
    }
}
```

코드 구현-DFS ⇒ 시간초과

class Solution {
    int min = Integer.MAX_VALUE;
    boolean arrive=false;
    public int solution(int[][] maps) {
        int n=maps.length;
        int m=maps[0].length;
        dfs(maps,0,0,n,m,1);
        return arrive?min:-1;
    }
    public void dfs(int[][] maps,int row,int col,int n,int m,int go){
        if(row<0 || row>=n || col<0 || col>=m || maps[row][col]!=1){
            return;
        }
        if(row==n-1&&col==m-1){
            arrive=true;
            min=Math.min(min,go);
            return;
        }
        maps[row][col]=0;
        //상하좌우
        dfs(maps,row-1,col,n,m,go+1);
        dfs(maps,row+1,col,n,m,go+1);
        dfs(maps,row,col-1,n,m,go+1);
        dfs(maps,row,col+1,n,m,go+1);
        //여러 경우를 따질 때 돌아와서 되돌려놓기(이경우는 끝까지 다 돌고임)
        maps[row][col] = 1;
        
    }
}

배우게 된 점

-완전탐색이고, 목적지가 명확히 존재한다면 BFS,DFS 둘 다 활용가능하지만 최단거리는 dfs 사용 시 시간초과가 발생했음

-인접리스트 형태로 바꾸어보기도 했는데, 그 후가 뭔가 익숙지않다. (결국 큐의 구조와 비슷하다고 느꼈음-어차피 다 같은 구조긴 하다.)

-문제를 보고 그래프를 잘 해석하는 것이 첫번 째. 어떤 것을 활용할지 고민하는 과정에서 아직 문제 경험이 적어 bfs를 어떻게 구현하나 머리가 복잡했는데, dfs로 풀며 구조가 눈에 익으니 bfs로 다시 푸는 것이 훨씬 수월했다.

-코드 써놓고 보면 참 짧다…