[코딩테스트] 프로그래머스 - 게임 맵 최단거리(Java, Level2) (dfs, 실패)

안녕하세요. 오늘은 프로그래머스의 코딩테스트 연습 문제 중 '게임 맵 최단거리' 문제에 대한 글입니다.

보자마자 dfs를 생각했으나 결론은 실패했고 풀이를 보고 bfs로 구현해야한다는걸 배웠습니다.

 

그러나 dfs로 푼게 아까워 남겨놓는 풀이입니다.

테스트 결과는 정상이나 효율성을 통과하지 못한 코드입니다.

 

참고부탁드립니다~

 

해당 문제는

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

프로그래머스

링크를 참고해주시기 바랍니다.

 

import java.util.*;

class Solution {
    boolean[][]visited;
    int answer;
    public int solution(int[][] maps) {
        visited=new boolean[maps.length][maps[0].length];
        answer=Integer.MAX_VALUE;

        dfs(0,0,maps,0);
        if(answer==Integer.MAX_VALUE)
        {
            return -1;
        }            
        return answer;
    }
    public void dfs(int x, int y, int[][] maps, int count)
    {
        count++;
        if(x==maps.length-1&&y==maps[0].length-1)
        {
            //System.out.println(count);
            
            if(answer==0&&count>0)
                answer=count;
            else
                answer=Math.min(answer,count);
            return;
            
            
        }
        //x 한칸 앞으로
        if(x+1<maps.length)
        {
            if(visited[x+1][y]==false&&maps[x+1][y]==1)
            {
                //count++;
                visited[x+1][y]=true;              
                dfs(x+1,y,maps,count);
                visited[x+1][y]=false;
            }
        }
        
        //x 한칸 뒤로
        if(x-1>=0)
        {
            if(visited[x-1][y]==false&&maps[x-1][y]==1)
            {
                //count++;
                visited[x-1][y]=true;
                dfs(x-1,y,maps,count);
                visited[x-1][y]=false;
            }
        }
        
        //y 한칸 앞으로
        if(y+1<maps[0].length)
        {
            if(!visited[x][y+1]&&maps[x][y+1]==1)
            {
                //count++;
                visited[x][y+1]=true;
                dfs(x,y+1,maps,count);
                visited[x][y+1]=false;
                
            }
        }
        
        //y 한칸 뒤로
        if(y-1>=0)
        {
            if(visited[x][y-1]==false&&maps[x][y-1]==1)
            {
                //count++;
                visited[x][y-1]=true;
                dfs(x,y-1,maps,count);
                visited[x][y-1]=false;
            }
            
        }
    }
}

이상입니다. 계속 풀이만 보면서 하다가 제가 짠 dfs라는게 의미가 크지만 너무 아쉽네요.

 

감사합니다:D