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

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

 

처음 짠 코드

class Solution {
   static int[] dx = {-1,1,0,0};
	    static int[] dy = {0,0,-1,1};
	    static int[][] arr;
	    static boolean[][] visited;
	    static int min= Integer.MAX_VALUE;
	    static int row;
	    static int col;
	    static int solution(int[][] maps) {
	        int answer = 0;
	        arr = maps;
	        row= maps[0].length;
	        col= maps.length;
	        visited = new boolean[row][col];
	        dfs(0,0,1);
	     
            if(min == Integer.MAX_VALUE){
                min=-1;
            }
	        return min;
	    }
	    static void dfs(int x,int y,int cnt){
	        if(visited[x][y]) return;
	        if(x==row-1 && y==col-1){
	            min = Math.min(min,cnt);
	            return;
	        }
	        for(int i=0; i<4; i++){
	            int nx = x + dx[i];
	            int ny = y + dy[i];

	                 if(nx>=0 && nx<row && ny>=0 && ny<col){
	     	            if(arr[nx][ny]==1){
	                if(!visited[x][y]){
	                    visited[x][y]= true;
	                    dfs(nx,ny,cnt+1);
	                    visited[x][y]=false;
	                }
	            }
	            }
	           
	        }
	    }
}

어떻게 고쳤어야 했나

최단거리면 무조건 bfs인데

dfs로 풀다니

bfs로 우선 바꿔보자

import java.util.*;
class Solution {
		static int[] dx = { -1, 1, 0, 0 };
		static int[] dy = { 0, 0, -1, 1 };
		static int[][] arr;
		static int[][] visited;
		static int min = Integer.MAX_VALUE;
		static int row;
		static int col;

		static int solution(int[][] maps) {
			int answer = 0;
			arr = maps;
			row = maps.length;
			col = maps[0].length;
			visited = new int[row][col];
			bfs();

			min = visited[row - 1][col - 1];
			if (min == 0)
				min = -1;

			return min;
		}

		static void bfs() {
			visited[0][0] = 1;
			Queue<int[]> q = new LinkedList<>();
			q.add(new int[] { 0, 0 });
			while (!q.isEmpty()) {
				int[] cur = q.poll();
				int x = cur[0];
				int y = cur[1];
				for (int i = 0; i < 4; i++) {
					int nx = x + dx[i];
					int ny = y + dy[i];

					if (nx >= 0 && nx < row && ny >= 0 && ny < col) {
						if (arr[nx][ny] == 1 && visited[nx][ny] == 0) {

							visited[nx][ny] = visited[x][y] + 1;
							q.add(new int[] { nx, ny });

						}
					}

				}
			}

		}

		}

 

 

완성코드!