[자바/Java] 프로그래머스 - 게임 맵 최단거리 (Level2 - DFS/BFS로 풀이)

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

프로그래머스

DFS

public class Solution {
    int[] x_list={0,0,1,-1};
    int[] y_list={1,-1,0,0};

    int[][] visited;
    int min_cnt = -1;
        
     public int solution(int[][] maps) {
         visited = new int[maps.length][maps[0].length];
         int answer = 0;

        dfs(0,0, maps, visited, 1);            
        
         return min_cnt;
     }
    
    public int dfs (int x, int y, int[][] maps, int[][] visited, int cnt){
        int height = maps.length;
        int width = maps[0].length;

        if(x == height-1 && y == width-1){ 
            if (min_cnt== -1){
                min_cnt=cnt;
                return 0;
            }
            else if (min_cnt > cnt){
                min_cnt=cnt;
                return 0;
            }
        } 
        int tempx=x;
        int tempy=y;
        for(int i =0;i<4;i++){
            tempx=x+x_list[i];
            tempy=y+y_list[i];
            if( (tempx>=0 && tempx<height) && (tempy>=0 && tempy<width) ){
                if(maps[tempx][tempy] == 1) {
                   if(visited[tempx][tempy] == 1) continue;

                    visited[tempx][tempy] = 1;

                    dfs(tempx, tempy, maps, visited, cnt+1);

                    visited[tempx][tempy] = 0;

                }
            }


        }

    return min_cnt;
    }
    
}

 

 

import java.util.*;

class Solution {
    
    Queue<WillVisit> queue = new LinkedList<WillVisit>();
    int[][] visited;
    int[] xArr = { 0 , 0 , -1, 1};
    int[] yArr =  {-1, 1, 0, 0};
    
    
    public int solution(int[][] maps) {
        int answer = -1;
        int height = maps.length;
        int width= maps[0].length;
        visited = new int[height][width];

        WillVisit wv1 = new WillVisit(0,0,1);
        queue.add(wv1);
    
        while(!queue.isEmpty()){
            WillVisit wv = new WillVisit(0,0,0);
            wv = queue.poll();
            
            if(wv.x == (height-1) && wv.y == (width-1)){
                return wv.cnt;        
            }
                
            for(int i=0; i<4; i++){
                int tmpx = wv.x +xArr[i];
                int tmpy = wv.y +yArr[i];
                if((tmpx >=0 && tmpx < height) 
                    && (tmpy >=0 && tmpy < width) ) {
                    if (maps[tmpx][tmpy] == 1 && visited[tmpx][tmpy] ==0 ){
                        
                        queue.add(new WillVisit(tmpx, tmpy, (wv.cnt)+1));
                        visited[tmpx][tmpy] = 1;
                        
                    }
                }
            }            
        }
    
        return answer;
    }
    
    
    
    class WillVisit {
        int x;
        int y;
        int cnt;
        
        public WillVisit(int x, int y, int cnt){
            this.x = x;
            this.y= y;
            this.cnt = cnt;
            
        }
    }
}