프로그래머스: 경주로 건설 [JAVA]

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/67259

코딩테스트 연습 - 경주로 건설

풀이

전체적인 풀이 과정은 다음과 같다.

1. 맵의 해당 위치 별로 방향마다 최소 비용을 저장하는 배열 생성
2. 위치 정보, 당시 비용, 방향성을 담은 위치 정보 클래스 생성
3. (0, 0)을 시작 위치로 bfs 탐색
4. 목표 지점에 도달할 경우 해당 비용과 답을 비교해 최소값으로 교체

 단순 bfs가 아니라 방향성을 따로 고려해야 하고, 기존대로의 중복 방문 여부 배열인 visited가 3차원이 되어야 해서 해결이 꽤나 어려웠던 문제이다.

 처음에는 단순히 중복 탐색 최소화를 위해 각 위치 별로 최소 비용을 담은 2차원 배열을 작성하여, bfs 탐색 도중 해당 위치에 도달했을 때의 비용이 배열에 저장된 비용보다 적은 경우에만 탐색을 이어갈 수 있도록 코드를 작성했다. 하지만 이렇게 작성했을 때 전체 테스트에서 마지막 문제만 틀렸는데, 찾아보니 특정 위치에서 비용이 더 비싸더라도 최종 지점에 도달했을 땐 비용이 더 적은 상황이 있다라는 점이었다. 그러다보니 해당 위치의 비용을 저장하는 배열에 변화를 주어야 했는데, 이 때 해당 지점에 도착했을 때의 방향성을 인자로 추가하여 각 위치마다 4가지 방향일 때의 비용을 따로 저장하는 것으로 했다. 이런 경우 동일한 방향성을 가지고 왔을 때만 값의 비교가 들어가고, 다른 방향과는 비교할 가능성이 없어 문제를 해결할 수 있었다.

 추가적으로 시작 위치에서는 어느 방향으로 가더라도 코너가 생기지 않고 모두 직선 도로였기에, 기존 동서남북에 대한 방향성을 0~3으로 배정하고 시작인 경우엔 4로 지정하여 비용 추가에 이상이 생기지 않도록 작성하였다.

class Solution {
    int[][][] pointCost;
    int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public int solution(int[][] board) {
        int answer = 999999999, length = board.length;
        Queue<Point> q = new LinkedList<>(); //bfs용 큐

        pointCost = new int[length][length][4]; //각 위치별 값 저장(방향 포함)
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                Arrays.fill(pointCost[i][j], 999999999);
            }
        }
        Arrays.fill(pointCost[0][0], 999999999);

        q.add(new Point(0, 0, 0, 4)); //bfs 탐색 시작

        while (!q.isEmpty()) {
            Point p = q.poll();

            //지정된 위치 밖 or 벽
            if (p.row >= length || p.row < 0 || p.col >= length || p.col < 0 || board[p.row][p.col] == 1)
                continue;

            //목표 지점 도달
            if (p.row == length - 1 && p.col == length - 1)
                answer = Math.min(answer, p.cost);

            //시작 제외 현재 비용이 해당 위치 최소값보다 크다면
            if (p.direction != 4 && p.cost >= pointCost[p.row][p.col][p.direction])
                continue;

            //해당 위치 가격 최신화
            if (p.direction != 4)
                pointCost[p.row][p.col][p.direction] = p.cost;

            for (int i = 0; i < 4; i++) {
                Point point = new Point(p.row + dir[i][0], p.col + dir[i][1], 0, i);

                if (p.direction == 4) {//시작인 경우 방향 상관없이 모두 +100원
                    point.cost = p.cost + 100;
                } else {
                    if (p.direction == i) {//방향이 동일한 경우 = 직선 도로
                        point.cost = p.cost + 100;
                    } else {//방향이 다른 경우 = 직선 도로 and 코너
                        point.cost = p.cost + 600;
                    }
                }

                q.add(point);
            }
        }

        return answer;
    }

    class Point {//위치 정보 클래스
        int row, col, cost, direction;

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

결과