99클럽 코테 스터디 33일차 TIL , 리코쳇 로봇

문제

풀이

입력으로  지도가 주어진다. D는 벽이고 R은 시작 지점 G는 도착지점 .은 이동가능 지역이다.

이동할 때는 스르륵 미끄러져 이동한다. 벽을 만나거나 지도의 끝 부분에 닿았을 때만 멈출 수 있다.

R에서 시작하여  G까지 갈 수 있는 경우 중 최소값을 리턴하면 된다.

만약 G까지 도달 할 수 없는 경우에는 -1을 return 한다.

 

제출 1 - 오답

class Solution {
    private int answer = Integer.MAX_VALUE;
    private boolean[][] visited;
    private static final int[] DX = {-1,0,1,0};
    private static final int[] DY = {0,1,0,-1};

    public int solution(String[] board) {

        int rowSize = board.length;
        int colSize = board[0].length();
        visited = new boolean[rowSize][colSize];
        for(int i=0;i<rowSize;i++){
            for(int j=0;j<colSize;j++){
                if(board[i].charAt(j) == 'R') dfs(board, i, j, -1, 0);
            }
        }
        if(answer == Integer.MAX_VALUE) answer = -1;
        return answer;
    }
    private void dfs(String[] board, int row, int col, int come, int cnt){
        if(cnt >= answer) return;
        if(board[row].charAt(col) == 'G'){
            answer = Math.min(answer, cnt);
            return;
        }
        for (int i = 0; i < 4; i++) {
            int nx = row + DX[i];
            int ny = col + DY[i];
            if(nx >= 0 && ny >= 0 && nx < board.length && ny < board[0].length()
                && come != i && board[nx].charAt(ny) != 'D'){
                if(DX[i] == -1){    //상
                    while(nx != 0
                            && board[nx - 1].charAt(ny) != 'D'){
                        nx--;
                    }
                }else if(DY[i] == 1){   //우
                    while(ny + 1 != board[0].length()
                            && board[nx].charAt(ny+1) != 'D'){
                        ny++;
                    }
                }else if(DX[i] == 1){   //하
                    while(nx + 1 != board.length
                            && board[nx + 1].charAt(ny) != 'D'){
                        nx++;
                    }
                }else if(DY[i] == -1){  //좌
                    while(ny != 0
                            && board[nx].charAt(ny-1) != 'D'){
                        ny--;
                    }
                }


                if(visited[nx][ny]) return;
                
                visited[nx][ny] = true;
                if(i - 2 < 0){
                    dfs(board, nx, ny, i + 2, cnt+1);
                }else{
                    dfs(board, nx, ny, i - 2, cnt+1);
                }
                visited[nx][ny] = false;
            }
        }

    }
}

 

최단거리라서 BFS를 활용하려다가 감이 안 와서 DFS로 시도했다.

코드가 굉장히 긴데 핵심은 R에서 시작하여 이동 가능한 곳의 끝까지 이동한 후 visited를 바꿔주고 dfs를 재귀에 넣는다.

만약 G를 만나면 cnt 값을 넣는다. 그 후에 이동할 경우 answer 보다 크거나 같을 때는 return 해준다.

 

테스트케이스는 모두 통과하고 질문에 나와있는 반례도 통과를 하는데 5개의 검사가 시간초과가 발생한다.

통과하는 경우에도 시간이 굉장히 오래 걸린다.

다른 풀이(DFS)

class Solution {
    private int answer = Integer.MAX_VALUE;
    private int[][] minSteps;	//메모제이션
    private static final int[] DX = {-1, 0, 1, 0};
    private static final int[] DY = {0, 1, 0, -1};

    public int solution(String[] board) {
        int rowSize = board.length;
        int colSize = board[0].length();
        minSteps = new int[rowSize][colSize];	
        for (int i = 0; i < rowSize; i++) {
            for (int j = 0; j < colSize; j++) {
                minSteps[i][j] = Integer.MAX_VALUE;	//보드와 똑같은 크기로 초기화
            }
        }

        for (int i = 0; i < rowSize; i++) {
            for (int j = 0; j < colSize; j++) {
                if (board[i].charAt(j) == 'R') {
                    dfs(board, i, j, -1, 0);
                }
            }
        }

        return answer == Integer.MAX_VALUE ? -1 : answer;
    }

    private void dfs(String[] board, int row, int col, int comeDirection, int cnt) {
        // 현재 위치에 더 적은 횟수로 도달한 적이 있으면 탐색 종료
        if (cnt >= minSteps[row][col]) return;

        minSteps[row][col] = cnt;

        // 목적지 도달
        if (board[row].charAt(col) == 'G') {
            answer = Math.min(answer, cnt);
            return;
        }

        // 네 방향에 대해 탐색
        for (int i = 0; i < 4; i++) {
            if (i == comeDirection) continue; // 들어온 방향으로는 되돌아가지 않음

            int nx = row;
            int ny = col;

            // 장애물 또는 벽에 닿을 때까지 이동
            while (true) {
            	//같은 값을 계속해서 더해주면 한 방향으로만 이동
                int nextX = nx + DX[i];	
                int nextY = ny + DY[i];

                if (nextX < 0 || nextY < 0 || nextX >= board.length 
                        || nextY >= board[0].length() 
                        || board[nextX].charAt(nextY) == 'D') {
                    break;
                }

                nx = nextX;
                ny = nextY;
            }

            // 재귀적으로 DFS 호출
            dfs(board, nx, ny, (i + 2) % 4, cnt + 1); 
        }
    }
}

 

메모제이션을 통해 방문했던 곳마다 도달한 횟수를 기록하여 그 기록보다 낮을 시에는 바로 return 하니 속도가 빨라진다.

같은 값을 계속해서 더해주는 방법도 기발하다.

다른 풀이(BFS)

class Solution {
    private static final int[] DX = {-1, 0, 1, 0};
    private static final int[] DY = {0, 1, 0, -1};

    public int solution(String[] board) {
        int rowSize = board.length;
        int colSize = board[0].length();
        boolean[][] visited = new boolean[rowSize][colSize];

        int startX = -1, startY = -1;
        for (int i = 0; i < rowSize; i++) {
            for (int j = 0; j < colSize; j++) {
                if (board[i].charAt(j) == 'R') {
                    startX = i;
                    startY = j;
                    break;
                }
            }
        }

        return bfs(board, startX, startY, visited);
    }

    private int bfs(String[] board, int startX, int startY, boolean[][] visited) {
        int rowSize = board.length;
        int colSize = board[0].length();
        //첫 값 넣어줌
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{startX, startY, 0}); // {x, y, count}
        visited[startX][startY] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int row = current[0];
            int col = current[1];
            int cnt = current[2];

            if (board[row].charAt(col) == 'G') {	//도착지점에 닿으면 현재 cnt 배출
                return cnt;
            }

			//네 방향 탐색
            for (int i = 0; i < 4; i++) {
                int nx = row;
                int ny = col;

                while (true) {
                    int tempX = nx + DX[i];
                    int tempY = ny + DY[i];

                    if (tempX < 0 || tempY < 0
                            || tempX >= rowSize || tempY >= colSize
                            || board[tempX].charAt(tempY) == 'D') {
                        break;
                    }
                    nx = tempX;
                    ny = tempY;
                }
				
                //방문 한적이 없다면 true 변경하고 큐에 넣음
                if (!visited[nx][ny]) {
                    visited[nx][ny] = true;
                    queue.add(new int[]{nx, ny, cnt + 1});
                }
            }
        }

        return -1;
    }
}

 

이 로직을 왜 떠올리지 못했을까.. BFS를 아직 다 이해하지 못한 것 같다. 최단 거리를 구할 경우 BFS를 이용하는 거라고는 알고 있지만 명확하게 이해하지 못했으니 구현하지 못한 거다.

네 방향을 탐색하는 것은 똑같다. 네 방향을 탐색하면서 해당 자리에 올 수 있는 최단거리를 확인해 나가는 방식이다.

속도 또한 확실하게 DFS보다 우위에 있다.

 

TIL

• 조건을 설정하는 게 익숙해져 간다.
• DFS, BFS