건설회사의 설계사인 죠르디는 고객사로부터 자동차 경주로 건설에 필요한 견적을 의뢰받았습니다.
제공된 경주로 설계 도면에 따르면 경주로 부지는 N x N 크기의 정사각형 격자 형태이며 각 격자는 1 x 1 크기입니다.
설계 도면에는 각 격자의 칸은 0 또는 1 로 채워져 있으며, 0은 칸이 비어 있음을 1은 해당 칸이 벽으로 채워져 있음을 나타냅니다.
경주로의 출발점은 (0, 0) 칸(좌측 상단)이며, 도착점은 (N-1, N-1) 칸(우측 하단)입니다. 죠르디는 출발점인 (0, 0) 칸에서 출발한 자동차가 도착점인 (N-1, N-1) 칸까지 무사히 도달할 수 있게 중간에 끊기지 않도록 경주로를 건설해야 합니다.
경주로는 상, 하, 좌, 우로 인접한 두 빈 칸을 연결하여 건설할 수 있으며, 벽이 있는 칸에는 경주로를 건설할 수 없습니다.
이때, 인접한 두 빈 칸을 상하 또는 좌우로 연결한 경주로를 직선 도로 라고 합니다.
또한 두 직선 도로가 서로 직각으로 만나는 지점을 코너 라고 부릅니다.
건설 비용을 계산해 보니 직선 도로 하나를 만들 때는 100원이 소요되며, 코너를 하나 만들 때는 500원이 추가로 듭니다.
죠르디는 견적서 작성을 위해 경주로를 건설하는 데 필요한 최소 비용을 계산해야 합니다.
예를 들어, 아래 그림은 직선 도로 6개와 코너 4개로 구성된 임의의 경주로 예시이며, 건설 비용은 6 x 100 + 4 x 500 = 2600원 입니다.
또 다른 예로, 아래 그림은 직선 도로 4개와 코너 1개로 구성된 경주로이며, 건설 비용은 4 x 100 + 1 x 500 = 900원 입니다.
도면의 상태(0은 비어 있음, 1은 벽)을 나타내는 2차원 배열 board가 매개변수로 주어질 때, 경주로를 건설하는데 필요한 최소 비용을 return 하도록 solution 함수를 완성해주세요.
[제한사항]
- board는 2차원 정사각 배열로 배열의 크기는 3 이상 25 이하입니다.
- board 배열의 각 원소의 값은 0 또는 1 입니다.
- 도면의 가장 왼쪽 상단 좌표는 (0, 0)이며, 가장 우측 하단 좌표는 (N-1, N-1) 입니다.
- 원소의 값 0은 칸이 비어 있어 도로 연결이 가능함을 1은 칸이 벽으로 채워져 있어 도로 연결이 불가능함을 나타냅니다.
- board는 항상 출발점에서 도착점까지 경주로를 건설할 수 있는 형태로 주어집니다.
- 출발점과 도착점 칸의 원소의 값은 항상 0으로 주어집니다.
입출력 예
| board | result |
| [[0,0,0],[0,0,0],[0,0,0]] | 900 |
| [[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],[0,1,0,0,0,1],[0,0,0,0,0,0]] | 3200 |
문제 해설
기본골자는 DP문제이다.
A*나 다익스트라를 사용해도 풀 수 있을것 으로 추정된다.
가장 중요한 골자는, 풀 수 있어도 가중치 여부를 잘 판별하여 적립해야하는것 인데, 중요한 가중치중하나는, 코너를 가장 적게 만들어야 한다는 것 이다. 그럼으로, 전에 들어왔던 값에 대한 방향데이터를 활용하여 코너를 판별하고, 효율적인 알고리즘을 작성해야 하는데,
필요한 데이터는 전값, 현재값, 이후값 을 판별하여, 현재 노드가 코너를 몃개 생성하는지 여부이다.
가장 비효율적으로 동작했을때 의 경우는
바로전 노드와 바로 다음 노드가 코너를 생성하게 되는것 인데,
이 상황을 피하기 위해서 전노드, 현재노드, 후 노드의 코너 여부를 판별해야 한다.
첫 번째 시도
#include <string>
#include <vector>
#include <list>
using namespace std;
enum Move
{
Up,
Down,
Left,
Right,
Start
};
struct Node
{
int CanMove = 0;
float nowDistance = 0;
float moved = 0;
vector<int> HasPosition;
Move MovedPos;
Node* NextNode;
};
bool Compare(Node* a,Node* b) {
return a->nowDistance < b->nowDistance;
}
bool MovedChack(const vector<vector<Node>>& Map, const vector<int>& NowPos, const vector<int>& move)
{
if (NowPos[0] + move[0] >= 0 && NowPos[0] + move[0] < Map.size() &&
NowPos[1] + move[1] >= 0 && NowPos[1] + move[1] < Map[0].size() &&
(Map[NowPos[0]+move[0]][NowPos[1]+move[1]].CanMove == 0 ||
Map[NowPos[0] + move[0]][NowPos[1] + move[1]].CanMove == 3))
return true;
return false;
}
vector<int> OutMove(const Move& input)
{
switch (input)
{
case Up:
return vector<int>({ 0, -1 });
case Down:
return vector<int>({ 0, +1 });
case Left:
return vector<int>({ -1, 0 });
case Right:
return vector<int>({ +1, 0 });
}
}
float ManDis(vector<int> apos, vector<int> bpos)
{
return bpos[0] - apos[0] + bpos[1] - apos[1];
}
float Distance(Node* Start, Node* back, Node* Now, Node* target, Move move)
{
float A = ManDis(Start->HasPosition, Now->HasPosition);
float B = ManDis(Now->HasPosition, target->HasPosition);
Now->moved = back->moved;
if (back->MovedPos != move && back->MovedPos != Move::Start) {
Now->moved += 5;
}
float result = Now->moved;
return result + B + A;
}
void InsertData(Node* Start, Node* Back, Node* Now, Node* Target, Move move, list<Node*>& Nodes)
{
float dis = Distance(Start, Back, Now, Target, move);
if (Now->nowDistance == dis) return;
Now->NextNode = Back;
Now->nowDistance = dis;
Now->MovedPos = move;
Now->CanMove = 3;
Nodes.push_front(Now);
}
void Astar(vector<vector<Node>>& Lines, vector<int> Start, Node* Target)
{
list<Node*> NextNodes;
NextNodes.push_back(&Lines[Start[0]][Start[1]]);
NextNodes.front()->nowDistance = 0;
NextNodes.front()->MovedPos = Move::Start;
Node* StartNode = NextNodes.front();
vector<vector<int>> moved;
moved.emplace_back(OutMove(Move::Up));
moved.emplace_back(OutMove(Move::Down));
moved.emplace_back(OutMove(Move::Left));
moved.emplace_back(OutMove(Move::Right));
while (NextNodes.size() > 0)
{
Node* Now = NextNodes.front();
Now->CanMove = 2;
if (Now == Target) break;
NextNodes.pop_front();
vector<int> NowPosition = Now->HasPosition;
vector<int> move = OutMove(Move::Up);
if (MovedChack(Lines, NowPosition, move))
InsertData(StartNode, Now, &Lines[NowPosition[0] + move[0]][NowPosition[1] + move[1]], Target, Move::Up, NextNodes);
move = OutMove(Move::Down);
if (MovedChack(Lines, NowPosition, move))
InsertData(StartNode, Now, &Lines[NowPosition[0] + move[0]][NowPosition[1] + move[1]], Target, Move::Down, NextNodes);
move = OutMove(Move::Left);
if (MovedChack(Lines, NowPosition, move))
InsertData(StartNode, Now, &Lines[NowPosition[0] + move[0]][NowPosition[1] + move[1]], Target, Move::Left, NextNodes);
move = OutMove(Move::Right);
if (MovedChack(Lines, NowPosition, move))
InsertData(StartNode, Now, &Lines[NowPosition[0] + move[0]][NowPosition[1] + move[1]], Target, Move::Right, NextNodes);
NextNodes.sort(Compare);
}
}
int solution(vector<vector<int>> board) {
int answer = 0;
// 노드 정리
vector<vector<Node>> Lines(board.size(), vector<Node>(board[0].size()));
Node* Target = &Lines[Lines.size() - 1][Lines[0].size() - 1];
for (int i = 0; i < board.size(); i++)
for (int j = 0; j < board[0].size(); j++) {
Lines[i][j].CanMove = board[i][j];
Lines[i][j].HasPosition = vector<int>({ i, j });
}
Astar(Lines, vector<int>({ 0, 0 }), Target);
Move back = Target->MovedPos;
int corner = 0;
int Count = 0;
while (Target != nullptr && Target != &Lines[0][0])
{
if (Target->NextNode != nullptr && Target->NextNode->NextNode != nullptr)
{
if (Target->MovedPos != Target->NextNode->MovedPos)
corner++;
}
Count++;
Target = Target->NextNode;
}
return (corner * 500) + Count * 100;
}실패
A*를 사용하여 코드를 구현하였으나, 4방의 이동을 고려하지 못하고, 8방을 기준으로 설계하였다.
Cos거리를 구하는것 이 아니라, 멘하탄 거리만 사용하여 가중치를 생각했어야 한다.
그리고, 각 노드를 확인하여 객체를 추정하였을 때, 코너 다음에 바로 코너가 나타나는 형태를 추정하지 못하여 최소코너생성법칙을 따르지 못했다.
코너가 가장 적게 생성되어야 함으로, 탐색데이터를 여러개 생성하고 추정해야 한다.
즉, A*로 데이터를 탐색하였을 때, 현재 노드와 다음노드와 다다음노드를 추정하고, 추정결과를 따라서 다다음노드까지 의 이동을 작성해야한다.
아마 A*로 구현하는건 효율적이지 못한것 같다.
다익스트라 방식으로 노드이동방식 을 구현한다고 했을 때, 다음노드와 다다음노드를 추정하고, 이동하는 과정에서 각 노드에서의 이동방향을 측정하고, 이동된 노드에서 다음 노드로 이동할 때의 가중치를 전부다 연산해야 함으로,
예를들어 위 아래에서 들어오는 이동방향과 좌 우에서 들어오는 이동방향이 둘 다 있다고 가정하면,
위와 같은 상황이 나타난다고 해보자.,
빨간색 이동방향에 도달했을 때의 가중치와 파란색 이동방향에 도달했을 때의 가중치가 같다고 가정한 뒤,
해당 노드에 도달하는 방식은 고려하지 않고, 도달했을 때의 가중치가 1000으로 같을 때, 아래로 이동하게 되면 다다음 노드에서 2000의 가중치가 되고, 오른쪽으로 이동했을 때 가중치가 2100이 된다고 생각해보자.
A*방식에 대해서는 언제나 오른쪽 또는 아래쪽 으로만 이동하게 됨으로, 다다음 또는 다음 이동방향에 대해 판별할 수 없다.
그럼으로, 이동방향에 대한 조건항을 생각해서, 어차피 가장 최대의 거리가 나타나는 경우가 언제나 3개의 노드를 측정했을 때, 2개 이상의 코너가 나타나는 경우이기 때문에, 해당 경우와 그 밑 코너가 나타나는 경우 두개 를 전부다 측정해야 한다는 결과가 나온다.
두 번째 시도
#include <string>
#include <vector>
#include <list>
#include <map>
#include <algorithm>
using namespace std;
map<vector<int>, int> moved;
bool Con(vector<int> input1, vector<int> input2)
{
return input1[4] < input2[4];
}
bool ChackToLine(vector<int> input, vector<int> MaxSize)
{
if (input[0] >= 0 && input[0] <= MaxSize[0] &&
input[1] >= 0 && input[1] <= MaxSize[1])
return true;
return false;
}
void MakeLine(list<vector<int>>& lists, vector<int> Back, vector<int> size, int X, int Y, const vector<vector<int>>& board)
{
vector<int> newInput(5, 0);
newInput[0] = Back[0] + X;
newInput[1] = Back[1] + Y;
if (ChackToLine(newInput, size) && board[newInput[1]][newInput[0]] != 1 &&
!(Back[2] == newInput[0] && Back[3] == newInput[1]))
{
if (!(Back[2] == newInput[0] - 2*X || Back[3] == newInput[1] - 2*Y))
newInput[4] += 500;
newInput[4] += 100 + Back[4];
newInput[2] = Back[0];
newInput[3] = Back[1];
vector<int> key;
key.push_back(newInput[0]);
key.push_back(newInput[1]);
if (moved.count(key) == 0) moved[key] = newInput[4];
else if (moved[newInput] < newInput[4]) return;
lists.push_front(newInput);
}
}
int solution(vector<vector<int>> board) {
int answer = 0;
vector<int> NowPosition(5, 0);
list<vector<int>> lines;
lines.push_back(NowPosition);
vector<int> size(2, 0);
size[0] = board.size() - 1;
size[1] = board[0].size() - 1;
while ((*lines.begin())[1] != size[0] || (*lines.begin())[0] != size[1])
{
list<vector<int>>::iterator now = lines.begin();
MakeLine(lines, (*now), size, 1, 0, board);
MakeLine(lines, (*now), size, 0, 1, board);
MakeLine(lines, (*now), size, -1, 0, board);
MakeLine(lines, (*now), size, 0, -1, board);
lines.erase(now);
lines.sort(Con);
}
return (*lines.begin())[4];
}실패
위 가정하에 방향을 제한한다고 생각해야 하기 때문에, 시작노드와 목표노드 에 대한 가중치를 멘하탄 거리로 측정하게 하였다.
그러나, 첫 번째 시도에 작성한 대로, 현재에 따른 미래가중치를 측정하는 방식을 넣지 않았기 때문에 실패.
세 번째 시도
#include <string>
#include <vector>
#include <list>
#include <unordered_map>
#include <algorithm>
using namespace std;
unordered_map<string, int> moved;
bool Con(vector<int> input1, vector<int> input2)
{
return input1[4] < input2[4];
}
bool ChackToLine(vector<int> input, vector<int> MaxSize)
{
if (input[0] >= 0 && input[0] <= MaxSize[0] &&
input[1] >= 0 && input[1] <= MaxSize[1])
return true;
return false;
}
void MakeLine(list<vector<int>>& lists, vector<int> Back, vector<int> size, int X, int Y, const vector<vector<int>>& board)
{
vector<int> newInput(5, 0);
newInput[0] = Back[0] + X;
newInput[1] = Back[1] + Y;
if (ChackToLine(newInput, size) && board[newInput[1]][newInput[0]] != 1 &&
!(Back[2] == newInput[0] && Back[3] == newInput[1]))
{
if (!(Back[2] == newInput[0] - 2*X || Back[3] == newInput[1] - 2*Y))
newInput[4] += 500;
newInput[4] += 100 + Back[4];
newInput[2] = Back[0];
newInput[3] = Back[1];
string key;
key.push_back(newInput[0]);
key.push_back(newInput[1]);
key.push_back(newInput[2]);
key.push_back(newInput[3]);
if (moved.count(key) == 0) moved[key] = newInput[4];
else if (moved[key] < newInput[4]) return;
lists.push_front(newInput);
}
}
int solution(vector<vector<int>> board) {
int answer = 0;
vector<int> NowPosition(5, 0);
list<vector<int>> lines;
lines.push_back(NowPosition);
vector<int> size(2, 0);
size[0] = board.size() - 1;
size[1] = board[0].size() - 1;
while ((*lines.begin())[1] != size[0] || (*lines.begin())[0] != size[1])
{
list<vector<int>>::iterator now = lines.begin();
MakeLine(lines, (*now), size, 1, 0, board);
MakeLine(lines, (*now), size, 0, 1, board);
MakeLine(lines, (*now), size, -1, 0, board);
MakeLine(lines, (*now), size, 0, -1, board);
lines.erase(now);
lines.sort(Con);
}
return (*lines.begin())[4];
}실패
가장 근접한 시도였다.
그냥 단순하게 벡터에 모든 데이터를 때려박은 다음에, 현재, 과거 다음 노드를 전부 기입한다음, 세 개의 노드중 다음과 전 노드의 이동방향이 다르게 나타날 경우, 이동비용을 500 추가해버렸다.
또한, 연산중첩으로 인한 속도차이가 나타나지 않게 하기 위해, 현재 이동해야 하는 객체들에 대한 이동했는지 여부를 판별하는 Key를 기입한. 헤쉬 맵을 사용하였다.
map에 Key를 생성하는 방식은, 현재노드의 위치값, 다음노드에 이동하는 현재 노드의 전 노드 위치값을 기입했다.그럼으로써, 현재 노드가 어떤방향에서 출발했는지 데이터를 기입할 수 있다.
그래도, 11번 문제에서 시간초과가 나타나서 최적화를 더 해야한다.
네 번째 시도
#include <string>
#include <vector>
#include <map>
#include <queue>
using namespace std;
map<string, int> moved;
class CustomComparator {
public:
bool operator() (const vector<int>& input1, const vector<int>& input2) const {
return input1[4] > input2[4];
}
};
bool ChackToLine(vector<int> input, vector<int> MaxSize)
{
if (input[0] >= 0 && input[0] <= MaxSize[0] &&
input[1] >= 0 && input[1] <= MaxSize[1])
return true;
return false;
}
void MakeLine(priority_queue<vector<int>, vector<vector<int>>, CustomComparator>& lists, vector<int> Back, vector<int> size, int X, int Y, const vector<vector<int>>& board)
{
vector<int> newInput(5, 0);
newInput[0] = Back[0] + X;
newInput[1] = Back[1] + Y;
if (ChackToLine(newInput, size) && board[newInput[1]][newInput[0]] != 1 &&
!(Back[2] == newInput[0] && Back[3] == newInput[1]))
{
if (!(Back[2] == newInput[0] - 2*X || Back[3] == newInput[1] - 2*Y))
newInput[4] += 500;
newInput[4] += 100 + Back[4];
newInput[2] = Back[0];
newInput[3] = Back[1];
string key;
key.push_back(newInput[0]);
key.push_back(newInput[1]);
key.push_back(newInput[2]);
key.push_back(newInput[3]);
if (moved.count(key) == 0) moved[key] = newInput[4];
else if (moved[key] < newInput[4]) return;
lists.push(newInput);
}
}
int solution(vector<vector<int>> board) {
int answer = 0;
// 노드 정리
vector<int> NowPosition(5, 0);
priority_queue<vector<int>, vector<vector<int>>, CustomComparator> lines;
lines.push(NowPosition);
vector<int> size(2, 0);
size[0] = board.size() - 1;
size[1] = board[0].size() - 1;
while (lines.top()[1] != size[0] || lines.top()[0] != size[1])
{
vector<int> now = lines.top();
lines.pop();
MakeLine(lines, now, size, 1, 0, board);
MakeLine(lines, now, size, 0, 1, board);
MakeLine(lines, now, size, -1, 0, board);
MakeLine(lines, now, size, 0, -1, board);
}
return lines.top()[4];
}성공
모든 값을 그대로 유지하되, 배열정리 방식을 바꾸었다.
list를 sort하는것 보다는 우선순위 큐를 사용해서 객체를 정리하는게 더 나았다.
map을 unordered_map에서 그냥 map으로 바꾸었는데, 이건 아마 코드 작성과정에서 실수가 있었던것 같다. 사실 unordered_map이 더 효율적임으로 바꾸는게 맞다.
추정컨데, list가 우선순위 큐 보다 느린 이유는, 우선순위 큐 의 경우에는 들어가면서 모든 노드를 검사하다가 이미 정렬되어있는 데이터 임으로, 정렬 중 자신의 위치가 나타나면 해당 위치에 기입되는데.
list.sort의 경우 모든 객체를 한번씩 전부 탐색하기 때문에 더 속도가 느린것 같다.
'코딩테스트 문제 풀이 > 동적계획법(Dynamic Programming)' 카테고리의 다른 글
| 마법의 엘리베이터 (0) | 2024.05.13 |
|---|---|
| 인사고과 (0) | 2024.05.08 |
| (2023 KAKAO BLIND RECRUITMENT) 택배 배달과 수거하기 (0) | 2024.04.25 |
| 뒤에 있는 큰 수 찾기 (0) | 2024.04.24 |
| 연속 펄스 부분 수열의 합 (0) | 2024.04.23 |