프로그래머스/3레벨

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

Koalitsiya 2024. 4. 1. 18:18
 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

  • 최단거리 문제
  • bfs로 해결
  • 현재 길의 정보에만 방향성을 추가하면 될 줄 알았으나 25번 케이스가 오답이 나와서 찾아보니cost 배열 자체에도 방향성을 저장할 필요가 있다고 해서 적용하니 해결됨

 

#include <string>
#include <vector>
#include <queue>

using namespace std;

// bfs를 수행하면서 전달하는 정보에 방향을 추가하면 될 것 같음

struct INFO {
    int x;
    int y;
    int cost;
    int dir;
};

int dirX[4] = {0, 1, 0, -1};
int dirY[4] = {1, 0, -1, 0};

int solution(vector<vector<int>> board) {
    int answer = INT32_MAX;
    
    int cost[4][26][26];
    
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 26; j++)
            for(int k = 0; k < 26; k++)
                cost[i][j][k] = INT32_MAX;
    
    queue<INFO> q;
    q.push({0, 0, 0, 0});
    cost[0][0][0] = 0;
    
    q.push({0, 0, 0, 1});
    cost[1][0][0] = 0;
    
    // bfs 수행
    while(!q.empty()) {
        INFO curINFO = q.front();
        q.pop();
        
        if(curINFO.x == board.size() - 1 && curINFO.y == board.size() - 1) {
            answer = min(answer, curINFO.cost);
            continue;
        }
        
        for(int i = 0; i < 4; i++) {
            int nx = curINFO.x + dirX[i];
            int ny = curINFO.y + dirY[i];
            
            if(nx >= 0 && nx < board.size() && ny >= 0 && ny < board.size()) {
                if(board[nx][ny] == 1) continue;
                
                int nCost;
                if(curINFO.dir == i) nCost = curINFO.cost + 100;
                else nCost = curINFO.cost + 600;

                if(nCost <= cost[i][nx][ny]) {
                    cost[i][nx][ny] = nCost;
                    INFO nextINFO = {nx, ny, nCost, i};
                    q.push(nextINFO);
                }
            }
        }
    }
    
    return answer;
}