[프로그래머스 2020 카카오 인턴십] 경주로 건설

문제

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

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

 

풀이

1. 이동하는 비용에 대해서 살펴보면 다음 칸으로 이동할 때의 방향이 현재 칸으로 이동한 방향과 같다면 비용이 100, 다르다면 600이고, 처음 시작지점에서는 어느방향으로 이동하던 비용이 100이라고 생각하면 됩니다.

 

2. $(0 , 0) -> (n - 1, n - 1)$로 이동할 때 최소비용을 찾는것이기에 방향에 상관없이 비용이 같다면 

  d[r][c] = (r,c)까지 오는데에 드는 최소비용 | 꼴로 상태를 표현하여 풀 수 있지만 위 문제의 경우 방향에 따라 비용이 다르기에

  d[r][c][dir] = (r,c)까지 dir방향으로 오는데에 드는 최소비용 | 꼴로 상태를 바꿔서 정의한다면 간단한 bfs를 통해 풀 수 있습니다.

 

코드

#include <bits/stdc++.h>
using namespace std;

const int dir[4][2] = { { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } };
const int inf = 0x3f3f3f3f;
typedef pair<int, int> pii;

int solution(vector<vector<int>> g) {
	int n, d[26][26][4], cr, cc, cdir, nr, nc, cost, nxtcost, ret = 1e9;
	n = g[0].size();
	memset(d, inf, sizeof(d));
	queue<pair<pii, pii>> q;
	q.push({ { 0,-1 },{ 0,0 } });
	d[0][0][0] = 0;
	while (!q.empty()) {
		cost = q.front().first.first, cdir = q.front().first.second;
		cr = q.front().second.first, cc = q.front().second.second; q.pop();
		for (int i = 0; i < 4; i++) {
			nr = cr + dir[i][0], nc = cc + dir[i][1];
			if ((!nr && !nc) || nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
			if (cdir == -1 || cdir == i) nxtcost = 100;
			else nxtcost = 600;
			if (cost + nxtcost <= d[nr][nc][i] && !g[nr][nc]) {
				d[nr][nc][i] = cost + nxtcost;
				q.push({ { d[nr][nc][i], i },{ nr,nc } });
			}
		}
	}
	for (int i = 0; i < 4; i++) ret = min(ret, d[n - 1][n - 1][i]);
	return ret;
}