C++ 프로그래머스 코딩테스트 - 경주로 건설 (67259)

경주로 건설

Level 3

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

프로그래머스

 

 

 

코너와 직선도로 비용을 다르게 계산해 도착 최소 비용을 찾는다.

 

 

 

직선 도로 하나를 만들 때는 100원이 소요되며, 코너를 하나 만들 때는 500원이 추가로 소요.
견적서 작성을 위해 경주로를 건설하는 데 필요한 최소 비용을 계산해야 한다.

 

 

 

 

나의 풀이

int solution(vector<vector<int>> board)
{
	int directx[] = { 0,0,1,-1 };
	int directy[] = { 1,-1,0,0 };
	int visit_minPriceCheck[25][25][4]{};
	set<int> arrivePriceList{};
	queue<vector<int>> q;
	q.push({ 0, 0, 0, -1 }); // x, y, price, direct
	board[0][0] = -1;
	while (!q.empty())
	{
		int cx = q.front()[0];
		int cy = q.front()[1];
		int price = q.front()[2];
		int direct = q.front()[3];
		q.pop();
		for (int k = 0; k < 4; ++k)
		{
			int nx = cx + directx[k];
			int ny = cy + directy[k];
			if (nx >= 0 && nx < board.size() && ny >= 0 && ny < board[0].size() && board[nx][ny] == 0 ) {
				int tmpPrice = price;
				if (direct != k/*방향이 바뀌었는지*/ && direct != -1 /*시작점*/)
					tmpPrice += 500; // 코너

				if (visit_minPriceCheck[nx][ny][k] != 0 && visit_minPriceCheck[nx][ny][k] < tmpPrice + 100)
					continue;
				visit_minPriceCheck[nx][ny][k] = tmpPrice + 100;
				q.push({ nx, ny, tmpPrice + 100, k });

				// 도착
				if (nx == board.size() - 1 && ny == board[0].size() - 1) 
					arrivePriceList.insert(tmpPrice + 100);
			}
		}
	}
	return *arrivePriceList.begin();
}

 

 

풀이 포인트는 BFS로 모든 경로 검색.

방문한 경로의 최소 비용을 저장할 때, 방향값도 같이 저장해줘야한다.