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

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

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

 

항상 DFS, BFS를 활용하는 문제를 어려워했었는데 일단 기본적인 문제를 통해서 조금의 감을 가질 수 있게 되었다. 아마 다른 문제들도 주제만 조금씩 바뀌고 엇비슷한 문제가 많은 것 같다.

그리고 이런 종류의 문제는 DFS/스택을 쓰면 최소거리를 구하는 경우의 수가 더 많아질 수도 있다고 하니 BFS를 이용하는 게 나을 것 같다. (BFS, 큐)

 

 

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

class Solution
{
    public int solution(int[][] maps)
    {
        int n = maps.length;
        int m = maps[0].length;
        int[][] visit = new int[n][m];
        Queue<int[]> q = new LinkedList<int[]>();
        int x = 0;
        int y = 0;
        
        visit[0][0] = 1;
        q.add(new int[]{0,0});
        
        while(!q.isEmpty())
        {
            int[] temp = q.poll();
            x = temp[0];
            y = temp[1];
            
            if((x+1<n) && maps[x+1][y]==1 && visit[x+1][y]==0)
            {
                visit[x+1][y] = visit[x][y]+1;
                q.add(new int[]{x+1, y});
            }
            if((x-1>=0) && maps[x-1][y]==1 && visit[x-1][y]==0)
            {
                visit[x-1][y] = visit[x][y]+1;
                q.add(new int[]{x-1, y});
            }
            if((y+1<m) && maps[x][y+1]==1 && visit[x][y+1]==0)
            {
                visit[x][y+1] = visit[x][y]+1;
                q.add(new int[]{x, y+1});
            }
            if((y-1>=0) && maps[x][y-1]==1 && visit[x][y-1]==0)
            {
                visit[x][y-1] = visit[x][y]+1;
                q.add(new int[]{x, y-1});
            }
        }
        
        return visit[n-1][m-1]==0?-1:visit[n-1][m-1];
    }
}