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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/67259

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

 

 

풀이

기본 베이스는 BFS이고 memoization 기법을 추가로 적용하여 풀이한다.

BFS에 사용될 큐는 2개의 pair로 이루어져 first의 first는 y좌표, second는 x좌표를 나타내고

second의 first는 방향, second는 비용을 나타낸다.

 

memoization을 적용하는 배열은 y, x좌표 뿐만 아니라 방향까지 저장하는 3차원 배열이어야 한다.

BFS로 순회할 때 이미 방문한 곳도 방향에 따라 비용이 달라지기 때문이다.

이미지 출처 : https://ansohxxn.github.io/programmers/117/

문제의 조건에서 직선 경로는 100원, 코너 경로는 600원이다. cost는 100을 기본으로 하며

상, 하로 이동하다가 좌, 우로 변경되거나 그 반대의 경우 500원을 cost에 더해주면 된다.

 

만약 비용이 메모되어있는 비용보다 작다면 업데이트해주고 이동한다.

BFS가 종료되면 memo[n-1][n-1][0] ~ memo[n-1][n-1][3]까지 방향별로 최소비용이 저장되어 있기 때문에

이 중 가장 작은 값을 리턴하면 된다.

 

코드

#include <bits/stdc++.h>
using namespace std;

#define INF 1e9

int dy[4] = { 1, 0, -1, 0 };
int dx[4] = { 0, 1, 0, -1 };
int memo[25][25][4];
int n, answer;

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

int solution(vector<vector<int>> board) {
    n = board.size();
    queue<pair<pair<int, int>, pair<int, int>>> q;
    //first for y, x & second for dir, cost
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            for(int k=0; k<4; k++){
                if(i == 0 && j == 0) memo[i][j][k] = 0;
                else memo[i][j][k] = INF;
            }
        }
    }
    
    q.push({{0, 0}, {-1, 0}});
    
    while(!q.empty()){
        pair<pair<int, int>, pair<int, int>> cur = q.front();
        q.pop();
        
        int y = cur.first.first;
        int x = cur.first.second;
        
        for(int i=0; i<4; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            int dir = cur.second.first;
            int cost = cur.second.second;
            cost += 100;
            
            if(!isInside(ny, nx) || board[ny][nx] == 1) continue;
            
            if(dir == 0 || dir == 2){
                if(i == 1 || i == 3){
                    cost += 500;
                }
            }
            else if(dir == 1 || dir == 3){
                if(i == 0 || i == 2){
                    cost += 500;
                }
            }

            if(cost < memo[ny][nx][i]){
                memo[ny][nx][i] = cost;
                q.push({{ny, nx}, {i, cost}});
            }
        }
    }
    
    answer = *min_element(memo[n-1][n-1], memo[n-1][n-1] + 4);
    
    return answer;
}