Today's Algorithm(2019-01-04)

programmers. 등굣길

지도 문제 그리고 최단거리를 보니 저도 모르게 bfs를 생각하게 되었습니다. 이러한 고정관념이 문제를 다양한 방식으로 생각하는 것을 막았던 것 같습니다.

 

그렇기 때문에 전형적인 bfs를 푸는 방식으로 큐를 이용하여 풀었습니다. 하지만 bfs는 최단거리를 찾는 것에 최적화된 것이지 '최단거리를 갈 수 있는 개수'에 대해서는 최적화되진 않았기 때문에 bfs코드에서 추가적인 조건이 붙었습니다. 그래서 목적지의 위와 옆에 왔을 때는 visit표시를 하지않고(만약 해버리면 다른 경우의 수가 무시되기 때문입니다) 그 개수를 세아렸습니다. 하지만 역시 어설픈 저의 조건인지 몇 개의 경우 오류가 났고 결정적으로 런타임 오류가 발생하였습니다.

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        boolean[][] visit = new boolean[n][m];
        int[] row = {0, 0, -1, 1};
        int[] col = {1, -1, 0, 0};
        Point target = new Point(n - 1, m - 1);
        Queue<Point> queue = new LinkedList<>();

        init(puddles, visit);
        queue.add(new Point(0, 0, 0));


        while (!queue.isEmpty()) {
            Point point = queue.poll();
            for (int i = 0; i < row.length; i++) {
                int nextRow = point.row + row[i];
                int nextCol = point.col + col[i];

                if (nextRow < 0 || nextRow >= n || nextCol < 0 || nextCol >= m) continue;
                if(nextRow == n - 1 && nextCol == m - 1) {
                    answer++;
                    answer = answer % 1000000007;
                    continue;
                }
                if (!visit[nextRow][nextCol]) {
                    queue.add(new Point(nextRow, nextCol, point.count + 1));
                    if(nextRow == n - 2 && nextCol == m - 1) continue;
                    if(nextRow == n - 1 && nextCol == m - 2) continue;
                    visit[nextRow][nextCol] = true;
                }
            }

        }
        return answer % 1000000007;
    }

    private void init(int[][] puddles, boolean[][] visit) {
        for (int[] puddle : puddles) {
            visit[puddle[0] - 1][puddle[1] - 1] = true;
        }
    }
}

class Point {
    int row;
    int col;
    int count;

    Point(int row, int col, int count) {
        this.row = row;
        this.col = col;
        this.count = count;
    }

    public Point(int row, int col) {
        this.row = row;
        this.col = col;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Point point = (Point) o;
        return row == point.row &&
                col == point.col;
    }
}

결국 위 코드가 통하는건 문제에서 주어진 테스트케이스 1개 밖에 없었으므로 틀린 코드였습니다.

 

다른 사람의 코드를 참고하면서 훨씬 쉽게 빠르게 풀 수 있는 방법을 알게되었습니다. 경로의 수를 위부터 더해 가는 것입니다!! 핵심내용을 간단히 정리해볼게요.(참고)

• 현재 포인트를 가는 가장 단거리는 바로 위쪽, 왼쪽에서 오는 2가지 경우입니다.
• 장애물이 있는 경우는 더할 때 0으로 더하면 더하는데 이상없습니다.
• 결국 장애물을 구별하는 변수 1개, 더하는 수들을 기록할 변수 1개 총 2개가 기본적으로 필요합니다.
• 0 base 인덱스는 혼란을 야기하니 배열 선언시 +1 더하여 1 base로 하는 것이 편합니다. 그리고 이 문제의 경우 더더욱 위, 왼쪽으로 더해야 하기 때문에 밖의 1겹이 더 있으면 훨씬 편합니다.

• 문제에서 말하는대로 1000000007을 나눠줘야 합니다. 즉 1000000007 을 초과하는 수가 계산 중에 계속 등장하기 때문이겠죠?

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] map = new int[n + 1][m + 1];
        int[][] d = new int[n + 1][m + 1];

        for (int[] puddle : puddles) {
            map[puddle[1]][puddle[0]] = -1;
        }

        d[0][1] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (map[i][j] == -1) {
                    d[i][j] = 0;
                } else {
                    d[i][j] = (d[i - 1][j] + d[i][j - 1]) % 1000000007;
                }
            }
        }
        return d[n][m];
    }
}

 

동적계획법 문제는 분명 문제에서 요구하는 방식이 있습니다. 그리고 효율적으로 풀수있는 최적의 방법이 있습니다! 이 문제는 예전에 백준에서 푼 문제같은데 다시 푸니 새롭네요.. 저희 알고리즘 실력은 늘고는 있는건지.. 저 스스로 자책을 하면서 또 다시 위로를 합니다.