[프로그래머스 lv3] 경주로 건설 풀이

 

해당 문제는 2020 카카오 인턴십 출제 문제로 공식 해설이 있습니다.

2020 카카오 인턴십 for Tech developers 문제해설

 

해설

dist[dir][x][y]를 dir 방향으로 (x, y)에 도달했을 때 최소 비용이라고 정의한다.

bfs로 좌표들을 탐색하면서 현재 위치에서 다음 위치로 도달할 때의 비용이 dist[dir][x][y]에 저장되어있는 값보다 작으면 갱신한다.

우리가 구하고 싶은 것은 (n-1, n-1)까지 도달하는데 최소 비용이므로, 상/하/좌/우 방향으로 도달한 dist[dir][x][y] 값 중에서 최솟값을 리턴하면 정답이다.

 

코드

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <climits>
#include <cctype>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

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

int n, d, x, y;
int dist[4][30][30];

bool OOB(int x, int y) {
    return x < 0 || x >= n || y < 0 || y >= n;
}

void setDist() {
    
    for (int k=0; k<4; k++) {
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++)
                dist[k][i][j] = 1e9;
        }
    }
}

int cost(int bfd, int nowd) {
    
    if (bfd == nowd) return 100;
    return 600;
}

void bfs(const vector<vector<int>>& board) {
    
    queue<iii> q;
    
    for (int i=0; i<4; i++) {
        dist[i][0][0] = 0;
        q.push({i, 0, 0});
    }
    
    while (!q.empty()) {
        
        iii cur = q.front();
        tie(d, x, y) = cur;
        q.pop();
        
        for (int i=0; i<4; i++) {
            int nx = x+dx[i];
            int ny = y+dy[i];
            if (OOB(nx, ny) || board[x][y]) continue;
            if (dist[d][x][y] + cost(d, i) < dist[i][nx][ny]) {
                dist[i][nx][ny] = dist[d][x][y] + cost(d, i);
                q.push({i, nx, ny});
            }
        }
    }
}

int solution(vector<vector<int>> board) {
    
    n = (int)board.size();
    setDist();
    bfs(board);
    
    int mn = 1e9;
    for (int i=0; i<4; i++) mn = min(mn, dist[i][n-1][n-1]);
    return mn;
}