[프로그래머스][C++] 경주로 건설 (257) (25번 반례 포함)

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

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

프로그래머스

 

생각의 흐름

사실 맨처음 문제를 보자마자 25*25 칸을 완전탐색해도 대각선 아래방향으로만 확인한다 치면, 25*25*3(온 방향의 반대 방향은 안가도 된다 생각) 의 경우를 모두 확인하면 된다 생각했다.

 

따라서 당연히 완전탐색으로 접근하게 되었고... 나름 순하게 풀려나갔다.

하지만 제출 결과 25번 테스트 케이스에서 통과를 할 수 없었다...

띠옹??? 25번은 왜???... (사실 여기서 나도 반례를 떠올릴수가 없었다... 다른 분들의 글을 읽다보니 다음과 같은 반례가 있었다)

 

▶ 25번 반례

vector<vector<int>> board = {{0, 0, 0, 0, 0, 0, 0, 0},
                             {1, 0, 1, 1, 1, 1, 1, 0},
                             {1, 0, 0, 1, 0, 0, 0, 0},
                             {1, 1, 0, 0, 0, 1, 1, 1},
                             {1, 1, 1, 1, 0, 0, 0, 0},
                             {1, 1, 1, 1, 1, 1, 1, 0},
                             {1, 1, 1, 1, 1, 1, 1, 0},
                             {1, 1, 1, 1, 1, 1, 1, 0}};

위 반례의 정답은 4500원이지만, 저의 코드에서는 4900원을 반환하고 있었습니다...

 

뭐가 문제였을까?

 

실패의 원인은

방향이 cost 에 영향을 주므로, 단순히 그 당시의 최소 비용을 저장하는 것이 아닌 방향정보를 포함해서 맵에 저장할 필요가 있다.

그래서 cost를 방향 정보와 함께 저장하도록 DP[25][25][4] 를 정의하여 사용해야 했다!

 

이를 그림으로 이해하여 보자!

출발을 (2, 1)에서 시작해서 (2, 3)에 도착한다고 해보자, 이때 방향이 동쪽으로 모두 동일했기 때문에 100원씩만 추가되서,

900 -> 1000 -> 1100 으로, 최종적으로는 1100원이 든다.

 

하지만 다음 (1,2)에서 내려오는 경우를 살펴보자.

만일 2차원 배열을 사용했었다면, 위 그림과 같이 (2, 2)지역은 800원으로 저장되어 버린다.

이유는 단순하게 900 > 800이기 때문이다. 가격 정보만 저장하기 때문에 값만 작다면 그 값을 저장하게 된다.

 

문제는 다음 상황이다.

이전에 800원 이라는 더 작은 값을 찾았기 때문에, 이를 기준으로 다음 지점들을 탐색하게 된다.

따라서 (2, 3) 지역이 1300원으로 값이 더 커져버렸다!

 

맨처음 -> 방향으로만 오는 경우가 1100원으로 더값이 작았다!

따라서 방향을 함께 고려하여 문제를 해결해나가야 합니다!

 

나의 코드

#include <bits/stdc++.h>

using namespace std;
// 방향, 시계방향 0123, 무방향 -1
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int DP[25][25][4];

class Car {
public:
    int x;
    int y;
    int cost;
    int dir;
public:
    Car(int x, int y, int cost, int dir) : x(x), y(y), cost(cost), dir(dir) {}
};

int solution(vector<vector<int>> board) {
    int answer = 2147000000;

    int N = board.size();
    int M = board[0].size();

    queue<Car> Q;
    Q.push(Car(0, 0, 0, 1));
    Q.push(Car(0, 0, 0, 2));

    for(int i = 0; i < 25; i++) {
        for(int j = 0; j < 25; j++) {
            for(int k = 0; k < 4; k++) {
                DP[i][j][k] = INT_MAX;
            }
        }
    }

    DP[0][0][1] = 0;
    DP[0][0][2] = 0;

    while (!Q.empty()) {
        Car &nowCar = Q.front();
        int nowX = nowCar.x;
        int nowY = nowCar.y;
        int nowCost = nowCar.cost;
        int nowDir = nowCar.dir;
        Q.pop();

        if (nowX == N - 1 && nowY == M - 1) {
            answer = min(answer, nowCost);
            continue;
        }

        for (int i = 0; i < 4; i++) {
            int nextX = nowX + dx[i];
            int nextY = nowY + dy[i];
            int add = 0;

            if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) continue;

            if (board[nextX][nextY] != 1) {
                if (nowDir == i) add = nowCost + 100;
                else add = nowCost + 600;

                if (DP[nextX][nextY][i] >= add) {
                    DP[nextX][nextY][i] = add;
                    Q.push(Car(nextX, nextY, add, i));
                }
            }
        }
    }

    return answer;
}