[C++/프로그래머스] 경주로 건설 (2020 카카오 인턴십)

문제

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

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

문제를 요약하자면,

정사각형 모양의 board에서

(0, 0)에서 (N-1, N-1)까지 경주로를 건설하는데

직선도로는 한 칸에 100원, 코너는 100+500 = 600원 비용이 발생한다.

 

따라서, (0, 0)에서 (N-1, N-1)까지 도로를 만들 수 있는 최소비용을 구하면 된다.

풀이

board의 최대 크기가 25x25이다. -> 엄청 크지 않음 -> 시간복잡도 널널 

그래서 일반적인 최단경로 찾기에 많이 쓰이는 BFS를 사용했다.

 

visited[r][c] 형태의 배열에 [0][0] ~ [r][c] 까지의 최소비용을 저장했다. 

그리고, Queue에 { r, c, cost, flag(방향정보) }를 담았다. 

 

그런데! visited를 2차원 배열로 이용했더니 테케 25번만 틀리게 나왔다 ㅜㅜ

질문하기에서 해답을 얻을 수 있었는데, 

직전에 0(상하) 방향으로 오든, 1(좌우) 방향으로 오든 [r][c]까지 필요한 cost는 동일할 수 있으나,

[r][c]에서 다음 칸으로 어떤 방향으로 이동하느냐에 따라 정답이 달라질 수 있기 때문에 

방향정보까지 구분해서 최소비용을 저장해야 한다는 것이었다!

 

결과적으로 visited[r][c][flag(방향)] 형태로 이용하여 정답이 될 수 있었다. 

 

이 문제의 풀이를 몇 개 찾아보면 2차원 배열로 풀이한 것을 찾아볼 수 있는데, 25번 테케가 추가되기전에 풀이된 것 같다. (그대로 복붙하여 제출해보니 25번이 역시 틀리게 나왔다)

코드

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

using namespace std;
int sCost = 100; // 직선도로 비용
int cCost = 600; // 코너 비용

struct Node {
	int r; int c; int cost; bool flag; // 0: 상하, 1: 좌우
};

int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,-1,0,1 };

int BFS(vector<vector<int>> board) {
	int end = board.size() - 1;
	int N = board.size();
    //[r][c]지점에 오는데 필요한 최소비용 저장
	vector<vector<vector<int>>> visited(N, vector<vector<int>>(N, vector<int>(N, 987654321))); 
	queue<Node> q;
	visited[0][0][0] = 0;
    visited[0][0][1] = 0;
	if (board[1][0] == 0) {
		visited[1][0][0] = 100;
		q.push({ 1, 0, 100, 0 }); // 이전에 상하방향
	}
	if (board[0][1] == 0) {
		visited[0][1][1] = 100;
		q.push({ 0, 1, 100, 1 }); // 이전에 좌우방향 
	}

	while (!q.empty()) {
		Node temp = q.front();
		q.pop();
		
		for (int i = 0;i < 4;i++) {
            int newR = temp.r + dr[i];
			int newC = temp.c + dc[i];
			int newCost = temp.cost;
			bool newFlag = temp.flag;
			if (i % 2 == (int)temp.flag) {
				newCost += sCost;
			}
			else {
				newCost += cCost;
				newFlag = !newFlag;
			}
			if (newR < 0 || newR >= N || newC< 0 || newC >= N) continue;
			if (board[newR][newC] == 1) continue;
			if (visited[newR][newC][newFlag] < newCost) continue;
			visited[newR][newC][newFlag] = newCost;
			q.push({ newR, newC, newCost, newFlag });
		}
	}
	return min(visited[end][end][0], visited[end][end][1]);
}
int solution(vector<vector<int>> board) {
	int answer = 0;
	answer = BFS(board);
	return answer;
}

결과