고찰

DFS로 처음에 문제를 풀려고 했다.
근데 아무리 해도 시간초과가 나서 한참을 고민했다. (분명 최단거리 문제를 DFS로 풀수있는데 왜 안될까 ?)

결국 정답을 보고 나의 문제점을 알 수 있었다.

• 최단거리는 DFS보다는 BFS로 푸는게 맞다. (평소에 DFS로 문제를 많이 풀었고, 최단거리 문제도 DFS로 풀리긴 해서 그냥 DFS를 써서 풀려고 했는데 여기서 큰 문제가 발생했다.)
• 그건 바로 내가 이전에 한번이라도 방문한 곳에는 더 짧게 올 수 있는 경우만 추가적으로 더 진행을 해야하고 그 거리보다 더 멀게 온 경우는 더 이상 진행하지 말아야 하는데 나는 그런거 없이 일단 다 돌았으며 + 정답이 나온 경우에만 백트래킹이 적용이 되서 대부분의 문제에서 시간초과가 났다. 아마도 bfs로 풀었으면 위에서 말한 더 짧게 온 경우보다 먼 경우는 자연스럽게 고려가 되지 않으므로 답이 나왔을텐데 그냥 내 식견이 좁아서 그 부분을 보지 못한 것 같다. 역시 코테는 파면 팔수록 생각할게 많다.
• 그리고 dfs는 방향에 따라 한번이라도 멀게 돌았으면 다른 방향으로 갈 때 그것보다 더 짧게 가는 경우가 있으면 그 경우에도 모든 케이스를 다 돌아야 하므로 (엄청난 중복이 발생하므로) 시간이 오래 걸리지만 bfs는 진짜 최소한의 값으로만 돌기 때문에 중복계산이 되는 곳이 없다. 그러므로 빠르다. (내가 푼 코드들의 시간만 비교해봐도 많이 나면 약 50배의 시간 차이가 난다.)

DFS

import java.util.Arrays;

class Solution {
    int ROW, COL;
    int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int[][] visited;
    char[][] map;
    int[] start, goal;
    private int answer;

    public int solution(String[] board) {
        answer = Integer.MAX_VALUE;
        ROW = board.length;
        COL = board[0].length();
        visited = new int[ROW][COL];
        for (int[] ints : visited) {
            Arrays.fill(ints, Integer.MAX_VALUE);
        }
        this.map = new char[ROW][COL];

        for (int r = 0; r < ROW; r++) {
            for (int c = 0; c < COL; c++) {
                char ch = board[r].charAt(c);
                map[r][c] = ch;

                if (ch == 'R') {
                    start = new int[]{r, c};
                } else if (ch == 'G') {
                    goal = new int[]{r, c};
                }
            }
        }

        visited[start[0]][start[1]] = 0;
        dfs(start[0], start[1], 0);

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

    private void dfs(int curRow, int curCol, int cnt) {
        if (map[curRow][curCol] == 'G') {
            answer = Math.min(answer, cnt);
            return;
        }

        for (int direction = 0; direction < directions.length; direction++) {
            int[] nextRowCol = goStraight(curRow, curCol, direction);
            int nextRow = nextRowCol[0];
            int nextCol = nextRowCol[1];

            if (visited[nextRow][nextCol] <= cnt + 1) {
                continue;
            }

            visited[nextRow][nextCol] = cnt + 1;
            dfs(nextRow, nextCol, cnt + 1);
        }
    }

    private int[] goStraight(int curRow, int curCol, int direction) {
        while (true) {
            int nextRow = curRow + directions[direction][0];
            int nextCol = curCol + directions[direction][1];

            if (isOutOfMap(nextRow, nextCol) || map[nextRow][nextCol] == 'D') {
                break;
            }

            curRow += directions[direction][0];
            curCol += directions[direction][1];
        }

        return new int[]{curRow, curCol};
    }

    private boolean isOutOfMap(int nextRow, int nextCol) {
        return nextRow < 0 || nextRow >= ROW || nextCol < 0 || nextCol >= COL;
    }
}

BFS

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    int ROW, COL;
    int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    boolean[][] visited;
    char[][] map;
    int[] start, goal;
    private int answer;

    public int solution(String[] board) {
        answer = Integer.MAX_VALUE;
        ROW = board.length;
        COL = board[0].length();
        visited = new boolean[ROW][COL];
        this.map = new char[ROW][COL];

        for (int r = 0; r < ROW; r++) {
            for (int c = 0; c < COL; c++) {
                char ch = board[r].charAt(c);
                map[r][c] = ch;

                if (ch == 'R') {
                    start = new int[]{r, c};
                } else if (ch == 'G') {
                    goal = new int[]{r, c};
                }
            }
        }

        visited[start[0]][start[1]] = true;
        bfs(start[0], start[1], 0);

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

    private void bfs(int curRow, int curCol, int cnt) {
        Deque<int[]> deque = new ArrayDeque<>();
        deque.add(new int[]{curRow, curCol, cnt});

        while (!deque.isEmpty()) {
            int[] cur = deque.poll();
            int cR = cur[0];
            int cC = cur[1];
            int cCnt = cur[2];

            if (cR == goal[0] && cC == goal[1]) {
                answer = Math.min(answer, cCnt);
                return;
            }

            for (int direction = 0; direction < directions.length; direction++) {
                int[] nextRowCol = goStraight(cR, cC, direction);
                int nextRow = nextRowCol[0];
                int nextCol = nextRowCol[1];

                if (visited[nextRow][nextCol]) {
                    continue;
                }

                visited[nextRow][nextCol] = true;
                deque.add(new int[]{nextRow, nextCol, cCnt + 1});
            }
        }
    }

    private int[] goStraight(int curRow, int curCol, int direction) {
        while (true) {
            int nextRow = curRow + directions[direction][0];
            int nextCol = curCol + directions[direction][1];

            if (isOutOfMap(nextRow, nextCol) || map[nextRow][nextCol] == 'D') {
                break;
            }

            curRow += directions[direction][0];
            curCol += directions[direction][1];
        }

        return new int[]{curRow, curCol};
    }

    private boolean isOutOfMap(int nextRow, int nextCol) {
        return nextRow < 0 || nextRow >= ROW || nextCol < 0 || nextCol >= COL;
    }
}