[프로그래머스] 경주로 건설

20년도 상반기 카카오 인턴십 코딩테스트 문제 경주로 건설 문제풀이입니다.

경주로 건설

이 문제는 문제만 읽었을 땐 크게 어려운 문제는 아니다. 처음 시작부터 갈 수 있는 모든 경로를 찾아서 도착할 때 가장 적은 비용이 들게 하는 전형적인 dfs bfs와 같은 경로찾기 문제지만 다시 돌아올 수 있는 케이스를 생각해야한다.

이 문제를 처음 접했을 땐 아 단순한 dfs bfs 문제라고 생각했습니다. 따라서 처음에 dfs와 bfs로 접근하였는데 풀다보니 시간초과가 발생하며 틀린 케이스가 나오는것을 알 수 있었습니다…

따라서 곰곰히 생각을 해본 결과 다익스트라가 생각나게 되었고, 기존에 알던 다익스트라 공식에 넣어서 풀 수 있었습니다.

근데 분명 시험볼땐 모든 테케가 맞았는데 공개되고 틀리다고 나와서 엄청 당황했습니다… 이유를 찾아본 결과 전 Dist[26][26]으로만 체크를 했었는데 모든 방향에 대해서 다르게 생각했어야 했습니다.

따라서 Dist 계산을 [26][26][4]로 늘려서 비교하게 되었고, 해결할 수 있었습니다.

Source Code :

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
//priority_queue

int Map[26][26];
int N;
int answer = 987654321;

int dx[4] = {-1,0,1,0}; // up right down left
int dy[4] = {0,1,0,-1};

int Dist[26][26][4];
vector<pair<int, int>> Arr[26][26];

struct info {
	int x, y, cost, dir;
};

struct cmp {
	bool operator()(info a, info b) {
		return a.cost > b.cost;
	}
};
int solution(vector<vector<int>> board) {

	N = board.size();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			Map[i][j] = board[i][j];
		}
	}

	priority_queue<info, vector<info>, cmp> pq;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			for (int m = 0; m < 4; m++) {
				Dist[i][j][m] = 987654321;
			}
		}
	}

	pq.push({ 0,0,0,1 });
	pq.push({ 0,0,0,2 });

	Dist[0][0][1] = 0;
	Dist[0][0][2] = 0;

	while (!pq.empty()) {
		int curx = pq.top().x;
		int cury = pq.top().y;
		int cost = pq.top().cost;
		int dir = pq.top().dir;
		pq.pop();

		for (int i = 0; i < 4; i++) {
			int nx = curx + dx[i];
			int ny = cury + dy[i];
			
			if (nx < 0 || nx >= N || ny < 0 || ny >= N)continue;
			if (Map[nx][ny] == 1)continue;

			int plus_cost = 0;

			
			if (dir % 2 == 0) { // up down
				if (i % 2 == 0)
					plus_cost = 100;
				else
					plus_cost = 600;
			}
			else { // left right
				if (i % 2 == 0)
					plus_cost = 600;
				else
					plus_cost = 100;
			}
			
			if (Dist[nx][ny][i] >= Dist[curx][cury][dir] + plus_cost) {
				Dist[nx][ny][i] = Dist[curx][cury][dir] + plus_cost;
				pq.push({ nx,ny,Dist[nx][ny][i],i });
			}
		}
	}

	for (int i = 0; i < 4; i++) {
		answer = min(answer,Dist[N - 1][N - 1][i]);
	}

	return answer;
}

Summary

• 실제 시험에서 맞았다고 자만하면 안된다는 생각을 하였다.
• 좀 쉽고 적용 가능한 문제더라도 깊이있게 생각하는것을 배우자.

소스코드

이 외에도 제가 푼 문제들 소스코드는 다음 링크에 있습니다!!! 알고리즘 문제풀이