C++ / 프로그래머스 / 경주로 건설

문제

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

프로그래머스

문제풀이

 

처음에 2차원, DFS를 이용해 문제를 풀었는데 테스트 케이스 하나가 계속 통과가 안 됐다.

질문글을 보니 방향 순서를 바꾸면 된다 해서 바꾸고 돌렸더니 이번엔 다른 테스트 케이스가 통과가 안 됐다.

그래서 다른 질문글을 보고 다른 풀이를 참고하여 3차원, DFS를 이용해 문제를 풀었다.

3차원이 되면서 추가되는 점은 다음으로 넘어갈 때 방향을 추가로 고려한다는 점이다.

알고리즘은 크게 어렵지는 않다.

 

다음 칸으로 넘어갈 때 벽인지 아닌지를 구분하고, 이전에 온 방향과 다음으로 갈 방향이 다르면 도로 건설비용 외 500원을 추가해야 한다. (기본 도로는 100, 코너는 600인셈)

이번 칸이 끝이라면 answer을 작은 값으로 초기화한다.

 

코드

#include <string>
#include <vector>
#define MAX 1000000
using namespace std;

int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };

vector<vector<int>>road;
vector<vector<vector<int>>>visited;
int answer(MAX);

void DFS(int y, int x, int cost, int prev) {
    int idx(0), ny(0), nx(0), n_cost(0);
    if (y == road.size() - 1 && x == road[0].size() - 1) {
        answer = min(answer, cost);
        return;
    }
    for (idx = 0; idx < 4; ++idx) {
        ny = y + dy[idx];
        nx = x + dx[idx];
        n_cost = cost + 100;
        if (0 <= ny && ny < road.size() && 0 <= nx && nx < road[0].size()) {
            if (road[ny][nx] == 1) continue;
            if ((prev == 0 || prev == 1) && (idx == 2 || idx == 3)) {
                n_cost += 500;
            }
            else if ((prev == 2 || prev == 3) && (idx == 0 || idx == 1)) {
                n_cost += 500;
            }

            if (visited[idx][ny][nx] > n_cost) {
                visited[idx][ny][nx] = n_cost;
                DFS(ny, nx, n_cost, idx);
            }
        }
    }
}


int solution(vector<vector<int>> board) {
    int idx(0);
    road = board;
    visited = vector<vector<vector<int>>>(4, vector<vector<int>>(road.size(), vector<int>(road[0].size(), MAX)));

    for (idx = 0; idx < 4; ++idx) {
        visited[idx][0][0] = 0;
    }

    DFS(0, 0, 0, -1);

    return answer;
}