[2020 카카오 인턴십] 경주로 건설

programmers.co.kr/learn/courses/30/lessons/67259

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

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

using namespace std;

const int dx[] = { -1, 0, 0, 1 };
const int dy[] = { 0, 1, -1, 0 };
struct path {
	int prevX, prevY, x, y;
};

int solution(vector<vector<int>> board) {
	int n = board.size();

	int price[2][25][25];
	fill(&price[0][0][0], &price[1][24][24] + 1, 1000000);
	price[0][0][0] = 0;
	price[1][0][0] = 0;

	queue<path> q;
	if (!board[1][0]) q.push({ 0, 0, 1, 0 });
	if (!board[0][1]) q.push({ 0, 0, 0, 1 });

	while (!q.empty()) {
		int prevX = q.front().prevX;
		int prevY = q.front().prevY;
		int x = q.front().x;
		int y = q.front().y;
		int prevRow = prevX == x;
		int prevPrice = price[prevRow][prevX][prevY];
		q.pop();

		for (int i = 0; i < 4; i++) {
			int newX = x + dx[i];
			int newY = y + dy[i];
			int row = x == newX;

			if (newX < 0 || newX >= n || newY < 0 || newY >= n) continue;
			if (board[newX][newY] == 1) continue;

			if (prevRow == row) {
				if (prevPrice + 100 <= price[row][x][y]) {
					price[row][x][y] = prevPrice + 100;
					q.push({ x, y, newX, newY });
				}
			}
			else {
				if (prevPrice + 600 <= price[row][x][y]) {
					price[row][x][y] = prevPrice + 600;
					q.push({ x, y, newX, newY });
				}
			}
		}
	}

	return min(price[0][n - 1][n - 1], price[1][n - 1][n - 1]);
}

 

실전에서 풀다가 풀다가 못풀었던 문제

근데 그때 짰던 로직이랑 지금 짠 로직이랑 차이가 없는데...?

뭐가 문제였을까.. 고것은 잘 모르겠다..