프로그래머스 - 경주로 건설 (Lv.3)

문제 링크

• 👉 경주로 건설

문제 설명

• N x N 크기의 격자가 주어지고, 각 격자의 칸은 비어 있거나(0) 또는 벽(1) 으로 채워진다.
• 출발점은 (0,0), 도착점은 (N-1, N-1) 이고, 출발점에서 도착점인 칸까지 중간에 끊기지 않고 경주로를 건설해야 한다.
• 인접한 빈 두칸을 연결하면 직선도로 이고, 두 직선도로가 직각으로 만나는 지점은 코너이다.
• 직선도로를 건설하는데 필요한 비용은 100원이고, 코너를 하나 만들때마다 500원씩 추가된다.
• 경주로 건설의 최소 비용을 구하라.

문제 접근

• BFS + DP 로 푼다.
• 모든 경주로 건설의 케이스를 조사하기 위해 BFS 를 쓴다.
• 어떤 방향 상태에서 다음 좌표로 이동했는지가 큐에 포함되어야 한다.
• 이동한 방향이 바꼈다면 600 의 비용이 들고, 같은 방향이라면 100 의 비용이 든다.
• 각 좌표까지 경주로를 건설하는데 필요한 최소 비용을 메모이제이션 기법으로 저장해두며 탐색을 진행한다.
  • 이때, 2차원 배열의 형태로만 비용을 관리하면 그 비용이 최소 비용인지 확신할 수 없다.
  • 각 좌표는 최대 4가지 방향에서 경주로가 건설될 수 있기 때문에, 각 방향에 대한 최소 비용을 계산해야 한다.
• (N-1, N-1) 점에서 최소 비용이 정답이 된다.

구현(All Pass)

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>

#define INF 9e8
using namespace std;

typedef struct _pos{
    int xpos;
    int ypos;
    int dir;
} Pos;

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

void bfs(vector<vector<int>> board, int sx, int sy, int dir){
    queue<Pos> q;
    Pos cpos = {sx, sy, dir};
    q.push(cpos);
    
    while(!q.empty()){
        cpos = q.front();
        q.pop();
        
        for(int dir=0; dir<4; dir++){
            int nx = cpos.xpos + dx[dir];
            int ny = cpos.ypos + dy[dir];
            if(nx<0 || nx>=N || ny<0 || ny>=N) continue;
            if(board[nx][ny]==1) continue;
            int ncst = 0;
            if(dir == cpos.dir) {
                ncst = cost[cpos.xpos][cpos.ypos][cpos.dir] + 100;
            }
            else{
                ncst = cost[cpos.xpos][cpos.ypos][cpos.dir] + 600;
            }
            if(cost[nx][ny][dir]==INF) {
                cost[nx][ny][dir] = ncst;
                q.push({nx, ny, dir});
            }
            else {
                if(ncst <= cost[nx][ny][dir]) {
                    cost[nx][ny][dir] = ncst;
                    q.push({nx, ny, dir});
                }
            }
        }
    }
    
}

int solution(vector<vector<int>> board) {
    int answer = INF;
    N = board.size();
    for(int r=0; r<N; r++){
        for(int c=0; c<N; c++){
            for(int dir=0; dir<4; dir++)
                cost[r][c][dir] = INF;
        }
    }
    for(int dir=0; dir<4; dir++)
        cost[0][0][dir]=0;
    
    // 출발점에서 가능한 방향은 2개 뿐이다.
    bfs(board, 0, 0, 1); // 남쪽
    bfs(board, 0, 0, 3); // 동쪽
    
    for(int dir=0; dir<4; dir++)
        answer = min(answer, cost[N-1][N-1][dir]);
    return answer;
}