경주로 건설 C++

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

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

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;
struct MOVE { int x, y; };
MOVE mv[4] = { { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } }; // 0:아래, 1:위, 2:우, 3:좌
struct INFO { int x, y, dir, sum; };
int answer = 2e9;
int money[30][30][4];

int solution(vector<vector<int>> board) {
	memset(money,-1,sizeof(money));

	queue<INFO> q;
	q.push({ 0,0,-1,0 });
	money[0][0][0] = 1;
    money[0][0][1] = 1;
    money[0][0][2] = 1;
    money[0][0][3] = 1;

	while (!q.empty()) {
		int i = q.front().x;
		int j = q.front().y;
		int d = q.front().dir;
		int s = q.front().sum;
		q.pop();

		if (i == (board.size() - 1) && j == (board.size() - 1)) {
			answer = min(answer, s);
			continue;
		}

		for (int k = 0; k<4; k++) {
			int mi = i + mv[k].x;
			int mj = j + mv[k].y;

			if (!(mi >= 0 && mi <board.size() && mj >= 0 && mj <board.size())) continue;
			if (board[mi][mj] == 1)  continue;

			int tmp = s;
			if (k == d || d == -1)  tmp += 100;
			else    tmp += 600;

			if (money[mi][mj][k] == -1 || money[mi][mj][k] > tmp) {
				q.push({ mi,mj,k,tmp });
				money[mi][mj][k] = tmp;
			}
		}
	}
	return answer;
}