프로그래머스/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;
}