리코쳇 로봇(프로그래머스-연습문제)

문제

코드

import java.util.*;
class Solution {
    int answer=Integer.MAX_VALUE;
    public int solution(String[] board) {
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length();j++){
                if(board[i].charAt(j)=='R')
                    dfs(i,j,i,j,0,board);
            }
        }
        if(answer==Integer.MAX_VALUE) return -1;
        return answer;
    }
    public void dfs(int r,int c,int lastR,int lastC,int count,String[] board){
        if(count>30) return;
        if(board[r].charAt(c)=='G'){
            answer=Math.min(answer,count);
            return;
        }
        
        if(r>0&&board[r-1].charAt(c)!='D'&&r-1!=lastR){
            int newR=r;
            while(newR>0&&board[newR-1].charAt(c)!='D')
                newR--;
            dfs(newR,c,newR+1,c,count+1,board);
        }
        if(r<board.length-1&&board[r+1].charAt(c)!='D'&&r+1!=lastR){
            int newR=r;
            while(newR<board.length-1&&board[newR+1].charAt(c)!='D')
                newR++;
            dfs(newR,c,newR-1,c,count+1,board);
        }
        if(c>0&&board[r].charAt(c-1)!='D'&&c-1!=lastC){
            int newC=c;
            while(newC>0&&board[r].charAt(newC-1)!='D')
                newC--;
            dfs(r,newC,r,newC+1,count+1,board);
        }
        if(c<board[0].length()-1&&board[r].charAt(c+1)!='D'&&c+1!=lastC){
            int newC=c;
            while(newC<board[0].length()-1&&board[r].charAt(newC+1)!='D')
                newC++;
            dfs(r,newC,r,newC-1,count+1,board);
        }
    }
}

풀이

최단거리 문제이다. 당연히 bfs를 사용해야 한다.
하지만, 제한사항에서 맵의 크기가 별로 크지 않아 나는 dfs로 해결했다.
(1) 맵을 순회하면서 시작지점을 찾는다. 시작 지점을 찾으면 dfs 탐색을 시작한다.(dfs() 함수의 매개변수는 현재 위치, 이전 위치, 이동 횟수, 맵 배열이 필요하다.)
(2) dfs() 함수에서는 다음을 수행한다.

• 현재 위치가 'G'이면 이동 횟수를 갱신하고 종료한다.
• 그렇지 않으면, 상하좌우로 탐색한다.(갈 수 있을 때까지 쭉 가야한다. 보통의 최단거리 문제와 다르다.)
• 상하좌우로 탐색하는데 매개변수로 들어왔던,이전 위치로 다시 가는 경우는 제외한다.(왔던 길로 다시 돌아가는 경우 제외)
• 이동 횟수가 30번을 넘어가면 그냥 끝낸다.

(3) dfs 탐색이 끝나면, answer을 반환한다.

결과

이거 나도 어떻게 이게 풀렸는지 모르겠다. 진짜 엉망으로 풀었다.
처음엔 당연히 bfs로 풀려고 했다. 근데 지금까지 봤던 최단거리 문제와 조금 달라 당황했다. 한칸씩 이동하는 것이 아니라, 벽이나 장애물을 만날때까지 가야했다. 지금 생각하면 bfs로 충분히 풀 수 있었는데 왜 나는 당시 bfs로 못 푼다고 생각했었는지 모르겠다.

그리고 dfs로 풀어도 사실 상관은 없다.
근데 사이클 처리를 내가 안했다.
사이클이 걸리는 경우를 방문 맵을 사용해서 체크 해주면 됐는데,
그 당시 나는 방문을 체크하면 지나갔던 길 전부를 다시 지나갈 수 없다고 생각해서, 방문 체크를 하면 안된다고 생각했다.
사실 도착한 지점 하나만 방문 표시를 해주면 된다.

그래서 나는 스택 오버플로우가 나길래 그냥 count를 최대 30으로 제한해버렸다. 아마 제한사항이 조금만 더 컸어도 무조건 오답일 풀이이다.

왜 이렇게 멍청하지
출처 : 프로그래머스 코딩 테스트 연습 https://school.programmers.co.kr/learn/challenges