programmers 경주로 건설 : programmers.co.kr/learn/courses/30/lessons/67259
코딩테스트 연습 - 경주로 건설
[[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[
programmers.co.kr
2020 카카오 인턴십에서 출제된 경주로 건설입니다.
Level 3에 해당하며, 기법으로는 다익스트라 알고리즘에 살짝(?)의 방향까지 생각해주셔야 합니다.
방향을 일방적으로 고려하시면 틀립니다!
이 문제에서 다익스트라를 구현할 실력이 되신다면 대부분 테스트케이스 14번?이 틀리게 될 것입니다.
14번 테스트케이스를 대략적으로 만들어보면 아래와 같습니다.
{0, 0, 0, 0, 0}
{0, 1, 1, 1, 0}
{0, 0, 1, 0, 0}
{1, 0, 0, 0, 1}
{0, 1, 1, 0, 0}
0,0을 기점으로 오른쪽으로 출발했을 때는 board[3][3]에서 2300을,
0,0을 기점으로 아래쪽으로 출발했을 때는 board[3][3]에서 2100을 갖게 될 것입니다.
당장 [3][3]에서 출발했을 때 2300을 기준으로 [4][4]에 도달하면 3000이 되고
2100을 기준으로 도달하면 3300이 됩니다.
'코너'가 한번 더 발생하기 때문입니다.
만약 방향을 일방적으로 고려한 다익스트라를 구현한다면,
[3][3]에서 2300을 꺼냈을 떄
다익스트라로 갱신한 최솟값 배열을 min_dist라고 한다면
이미 min_dist[3][3] 은 2100이기 때문에 continue되면서 탐색하지 않게 되겠죠,,
이정도 설명이면 충분히 이해하셨을 거라 생각합니다.
즉, 다익스트라를 통해 '그 지점의 방향'에 대한 최솟값을 가지고 계셔야 합니다.
min_dist[y][x][방향] 이렇게 3차원배열로 해결가능합니다.
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct pii {
int dist, y, x, way;
};
struct piicmp {
bool operator()(pii& A, pii& B) {
return A.dist > B.dist;
}
};
int my[4] = { -1,0,1,0 };
int mx[4] = { 0,1,0,-1 };
int arr[26][26][4];
int solution(vector<vector<int>> board) {
int answer = 987654321;
int bs = board.size();
for (int i = 0; i < bs; i++) {
for (int j = 0; j < bs; j++) {
for(int k = 0; k<4; k++){
arr[i][j][k] = 987654321;
}
}
}
priority_queue<pii, vector<pii>, piicmp> pq;
if (!board[0][1]) pq.push({ 0,0,0,1 });
if (!board[1][0]) pq.push({ 0,0,0,2 });
while (!pq.empty()) {
int y = pq.top().y;
int x = pq.top().x;
int dist = pq.top().dist;
int way = pq.top().way;
pq.pop();
if (arr[y][x][way] < dist) continue;
if (y == bs - 1 && x == bs - 1) {
answer = min(answer, dist);
}
for (int i = 0; i < 4; i++) {
int yy = y + my[i];
int xx = x + mx[i];
if (yy >= 0 && yy < bs && xx >= 0 && xx < bs && board[yy][xx] != 1) {
if (i == way) {
int distance = dist + 100;
if (distance < arr[yy][xx][i]) {
arr[yy][xx][i] = distance;
pq.push({ distance, yy, xx, way });
}
}
else if (i == (way + 1)%4 || i == (4 + way - 1)%4) {
int distance = dist + 600;
if (distance < arr[yy][xx][i]) {
arr[yy][xx][i] = distance;
pq.push({ distance, yy, xx, i });
}
}
}
}
}
return answer;
}'algorithm > programmers' 카테고리의 다른 글
| programmers [1차] 뉴스 클러스터링 c++ (0) | 2020.12.21 |
|---|---|
| programmers 무지의 먹방 라이브 (0) | 2020.12.20 |
| programmers 보석 쇼핑 (0) | 2020.12.16 |
| programmers 키패드 누르기 (0) | 2020.12.14 |
| programmers 수식 최대화 (0) | 2020.12.14 |