2020 카카오 인턴쉽 코딩테스트 4번 경주로 건설

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

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

2020 카카오 인턴쉽 코딩테스트에 4번에 출제되었었던 경주로 건설 문제이다.

위 링크를통하여 프로그래머스에서 풀어볼 수 있다.

 

아이디어

해당 문제는 bfs를 이용한 완전 탐색으로 풀이했는데, 현재 경로의 최솟값을 저장하고 있는 load 배열을 초기화하는 과정에서 엄청 시간이 오래 걸렸다. 처음 문제를 마주쳤을때 queue를 돌리는데 이동방향 표현만 해결되면 금방 풀이하겠다라는 생각을 가졌었는데 0 1 2 3로 방향 표현을 하고도 이상하게 틀리는 반례 케이스들이 존재했다. 손으로 한참 따라가며 생각해보고 나서야 현재 경로를 저장할때 x, y축 뿐만 아니라 최솟값일때 가고 있던 방향이 표현이 안되었구나라는 것을 느껴 성공을 받아냈다. 2일정도 고민을 해서 실제 코테였다면 맨탈이 갈려나갔을 것이다.

#include <string>
#include <vector>
#include <queue>
#define INF 987654321
using namespace std;

int N;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int load[4][25][25];


int min(int a, int b) { return a > b ? b : a; }

int solution(vector<vector<int>> board) {

	N = board.size();
	for (int c = 0; c < 4; c++) 
		for (int i = 0; i < N; i++) 
			for (int j = 0; j < N; j++) 
				load[c][i][j] = INF;

	int answer = INF;
	queue<pair<pair<int, int>, pair<int, int>>>q;
	q.push({ {0,0},{0,-1 } });
	for (int i = 0; i < 4; i++) {
		load[i][0][0] = 0;
	}
	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int cost = q.front().second.first;
		int dir = q.front().second.second;
		q.pop();
		if (y == N - 1 && x == N - 1)
			answer = min(answer, load[dir][y][x]-500);
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny >= N || ny < 0 || nx >= N || nx < 0) continue;
			if (board[ny][nx] == 1) continue;
			int newCost = cost + 100;
			if (dir != i) newCost += 500;

			if (newCost <= load[i][ny][nx]) {
				load[i][ny][nx] = newCost;
				q.push({ {ny,nx},{newCost,i} });
			}

		}
	}
	return answer;
}