프로그래머스 - 경주로 건설 (C++)

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

프로그래머스

 이 문제는 경주로를 건설한다고 할 때, 최소 비용을 구하는 문제이다. 이 때, 직선 도로는 100원이 들며 두 개의 직선 도로가 직각으로 만나는 코너는 500원이 든다. 즉, 직진하면 100원이 필요하고 방향을 직각으로  꺾어서 나아가면 600원이 필요할 때의 최소값을 구하는 문제이다. 처음에는 단순한 BFS 문제라고 생각하였다. 그래서 각 지점에서의 최소 비용을 저장할 2차원 배열을 minCost[MAX][MAX]라고 선언한 후, 평소 하던대로 갈 수 있는 곳이면서 비용이 더 적다면 진행하고 아니면 마는, 그러한 방식으로 진행하였다. 그런데 마지막 예제 25번에서 계속 틀렸었다.

 무슨 영문인가 싶어 혼자 계속 생각을 했지만 뭐가 틀린지 알 수 없었다. 그래서 이 문제와 관련된 질문들을 본 후, 뭐가 부족한지 알게 되었다. 어떤 지점을 회전에서 들어오느냐, 그냥 들어오느냐에 따라 그 다음 지점에서의 비용이 달라질 수 있다는 사실을 간과하였다. 하지만 이런 식으로 방향에 따른 미래를 고려하면서 BFS를 진행할 자신이 없었다. 그래서 위의 2차원 배열을 조금 수정하였다. 각 지점에서, 각 방향에 따른 최소 비용을 저장할 수 있게  minCost[MAX][MAX][4], 3차원 배열로 바꾸었다. 이렇게 바꾸는 것으로, 모든 방향에 따른 최소 비용을 구할 수 있었기 때문에 이 문제를 풀 수 있었다.

1. 탐색의 편의를 위해, 모든 지점에서, 모든 방향에서의 최소 비용을 저장할 배열의 값을 최대한 크게 설정한다.
2. BFS를 진행한다.
   1. 큐에는 r좌표, c좌표, 현재 방향, 현재 비용이 저장된다.
   2. 시작 지점 (0, 0)에서 (0, 1), (1, 0)으로 진행할 수 있으므로, 나아갈 수 있다면 큐에 push한 후 반복문을 실행한다.
   3. 만약 도착점이라면, 비용을 비교하여 최소 비용을 갱신한다.
   4. 다음 방향을 반복문을 이용해 진행한다.
   5. 만약 다음 방향의 좌표가 board의 범위 안에 있으면서 방향에 따른 최소 금액이 맞다면, 그대로 진행한다.

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

using namespace std;

#define INF 987654321
#define MAX 26
#define STRAIGHT 100
#define CORNER 500

int N;  // board의 한 변의 길이
int minCost[MAX][MAX][4];   // 각 지점의 방향에 따른 최소 비용

// 다음 방향을 위한 변수들. 순서대로 아래쪽, 왼쪽, 윗쪽, 오른쪽
int nr[4] = { 1, 0, -1, 0 };    
int nc[4] = { 0, -1, 0, 1 };  

// 현재 위치가 범위 안에 있는지를 반환
bool IsIn(int r, int c)
{
	return 0 <= r && r < N && 0 <= c && c < N;
}

// 두 개의 방향이 서로 반대 방향인지 (180도 회전하여 뒤로 돌아있는지)
bool TurnBack(int dir1, int dir2)
{
	// 0이랑 2는 서로 위아래 방향이라 뒤를 도는 방향
	// 1이랑 3은 서로 좌우 방향이라 뒤를 도는 방향
	// 즉, dir1과 dir2의 차이가 2라면 뒤를 돈다고 볼 수 있다.
	if (abs(dir1 - dir2) == 2)
		return true;
	else
		return false;
}

// 두 개의 방향이 서로 직각인지 (회전을 했는지))
bool Turn(int dir1, int dir2)
{
	// 뒤를 도는 경우
	if (TurnBack(dir1, dir2))	
		return false;

	// 직진인 경우
	if (dir1 == dir2)
		return false;

	// 그 외는 전부 회전한 경우이다.
	return true;
}

// 방향에 따른 추가 비용
int Cost(int dir1, int dir2)
{   
    // 만약 회전을 한다면 직선 도로 비용 + 코너 비용
	if (Turn(dir1, dir2))
		return STRAIGHT + CORNER;
	else    // 아니라면 직선 비용만
		return STRAIGHT;
}	

// 최소 비용을 찾기 위한 함수
int Search(vector<vector<int>> board)
{
	int answer = INF;
        
    // 큐에는 순서대로 r좌표, c좌표, 현재 방향, 현재 비용이 저장된다.
	queue<pair<pair<int, int>, pair<int, int>>> q;
	for (int dir = 0; dir < 4; ++dir)
		minCost[0][0][dir] = 0;
    
    // (0, 0)에서는 (1, 0), (0, 1)로 진행할 수 있으므로
    // 나아갈 수 있다면 진행한다.
	if (board[1][0] == 0)
	{
		q.push({ { 1, 0 }, { 0, STRAIGHT } });
		minCost[1][0][0] = STRAIGHT;
	}

	if (board[0][1] == 0)
	{
		q.push({ { 0, 1 }, { 3, STRAIGHT } });
		minCost[0][1][3] = STRAIGHT;
	}

	while(!q.empty())
	{
		int curR = q.front().first.first;
		int curC = q.front().first.second;
		int curDir = q.front().second.first;
		int curCost = q.front().second.second;
		q.pop();
        
        // 만약 도착점이라면, 비용을 비교하여 비용 저장
		if (curR == N - 1 && curC == N - 1)
		{
			if (answer > curCost)
				answer = curCost;
                    
            continue;   // 이 곳에서는 더 진행할 필요 없음
		}
        
        // 다음 방향을 반복문을 이용해 진행
		for (int nxtDir = 0; nxtDir < 4; ++nxtDir)
		{   
            // 만약 현재 방향에서 180도 회전한 방향이라면, 그냥 패스
			if (TurnBack(curDir, nxtDir))
				continue;
				
			int nxtR = curR + nr[nxtDir];
			int nxtC = curC + nc[nxtDir];
			int nxtCost = curCost + Cost(curDir, nxtDir);
    
			if (IsIn(nxtR, nxtC))
			{
				if (minCost[nxtR][nxtC][nxtDir] >= nxtCost && board[nxtR][nxtC] == 0)
				{
                    // 범위 안에 있으면서 방향에 따른 최소 금액이 맞다면 진행
					minCost[nxtR][nxtC][nxtDir] = nxtCost;
					q.push({ { nxtR, nxtC }, { nxtDir, nxtCost }});
				}
			}
		}
	}

	return answer;
}

int solution(vector<vector<int>> board)
{
    // 비교의 편의를 위해서, 모든 지점에서 모든 방향에서의 비용을 가능한 크게 설정.
	for (int r = 0; r < MAX; ++r)
	{
		for (int c = 0; c < MAX; ++c)
		{
			minCost[r][c][0] = INF;
			minCost[r][c][1] = INF;
			minCost[r][c][2] = INF;
			minCost[r][c][3] = INF;
		}
	}

	N = board.size();

	int answer = Search(board);
	
	return answer;
}

 

---

참고한 글: https://school.programmers.co.kr/questions/21325