Problem 문제풀이
스타트 택시라는 문제로 최근 푼 문제중에 제일 단순하다.
그러나 문제를 대충 읽는 바람에 푸는 데 한 시간이 걸리고 말았다.
여러분은 꼭 문제를 자세히 읽기 바란다. 조건 하나하나 꼼꼼히 말이다.
전략
-
운전자와 모든 승객간의 최단거리를 구하고 그 중 가장 가까운 승객에게 이동한다.
-
여기서 주의해야할 것은 거리가 가장 가까운 손님이 여러 명 존재할 경우
행이 작은 순으로 -
그 다음으로는
열이 작은 순으로 손님을 방문한다. 문제를 꼭 제대로 읽자!
-
-
손님한테 가는데 이동한 칸의 수만큼 연료가 줄어든다.
-
손님을 태우고 도착지까지 이동한 칸의 수만큼 연료가 줄어든다.
-
2,3에서 도중에 연료가 0이하가 되면 -1을 return한다. 단 3의 경우 도착과 동시에 0이 되는 것은 상관없다.
-
1~4를 반복한다.
-
만약 모든 손님을 목적지까지 무사히 이동시켰을 경우 남은 연료량을 return한다.
손님의 정보를 저장할 struct Passenger를 만들어보자.
변수로는 s_r, s_c, d_r, d_c(start row,col / destination row,col) 이렇게 4개이다.
struct Passenger {
int s_r, s_c, d_r, d_c;
Passenger(int _s_r, int _s_c, int _d_r, int _d_c) :s_r(_s_r), s_c(_s_c), d_r(_d_r), d_c(_d_c) {}
};
이제 두 좌표 간의 최단거리를 구하는 함수 Dist를 BFS를 사용하여 만들 것이다.
int Dist(int s_r, int s_c, int d_r, int d_c)
{
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
visited[i][j] = -1;
}
}
queue<pair<int, int>>q;
q.push({ s_r,s_c });
visited[s_r][s_c] = 0;
while (!q.empty())
{
pair<int, int>pos = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int nR = pos.first + dirR[i];
int nC = pos.second + dirC[i];
if (nR > 0 && nR <= N && nC > 0 && nC <= N)
{
if (visited[nR][nC] == -1 && city[nR][nC] == 0)
{
visited[nR][nC] = visited[pos.first][pos.second] + 1;
q.push({ nR ,nC });
}
}
}
}
return visited[d_r][d_c];
}
while문 안에서 pos가 목적지랑 일치하는 순간 값을 return해줘도 결과는 같을 것이다.
그러나 while문을 빠져 나오고 값을 return해준 이유는 시간절약을 위해서이다.
우리는 운전사와 모든 승객간의 거리를 구해야한다. 승객 한 명과의 거리만 구하고 끝내기에는
여태까지 Search한 것이 너무 아깝지 않은가? while문을 나왔다는 것은 도시 위에 있는 모든 좌표와의 최단 거리가
visited배열에 예쁘게 들어있다는 것을 의미한다. Dist는 한 번만 부르고 나머지 승객과의 거리는
이 visited배열을 활용하도록 하자! 이제 simulation함수이다.
int simulation(int oil)
{
if (passenger.empty())
{
return oil;
}
승객이 없을 경우에는 남은 oil을 return한다.
int minDistance = Dist(driver.first, driver.second, passenger[0].s_r, passenger[0].s_c);
int p_idx = 0;
for (int i = 1; i < passenger.size(); i++)
{
if (minDistance == -1 || minDistance >= visited[passenger[i].s_r][passenger[i].s_c])
{
if (minDistance == visited[passenger[i].s_r][passenger[i].s_c])
{
if (passenger[p_idx].s_r < passenger[i].s_r || (passenger[p_idx].s_r == passenger[i].s_r && passenger[p_idx].s_c < passenger[i].s_c))
{
continue;
}
}
minDistance = visited[passenger[i].s_r][passenger[i].s_c];
p_idx = i;
}
}
아까 이야기했듯이 Dist는 처음에 한 번 부른다. Dist의 return value가 -1이라는 것은 방문할 수 없다는 것을 의미한다.
현재 minDistance가 -1이거나 i번째 손님과의 거리가 minDistance보다 가까울 경우 minDistance를 갱신해준다.
혹시 두 값이 같을 경우 행이 더 작고 열이 더 작은 위치의 손님을 우선시한다.
if (minDistance == -1)
{
return -1;
}
oil -= minDistance;
if (oil <= 0)
{
return -1;
}
int cost = Dist(passenger[p_idx].s_r, passenger[p_idx].s_c, passenger[p_idx].d_r, passenger[p_idx].d_c);
if (cost == -1 || oil - cost < 0)
{
return -1;
}
oil += cost;
driver = { passenger[p_idx].d_r,passenger[p_idx].d_c };
passenger.erase(passenger.begin() + p_idx);
return simulation(oil);
}
모든 손님과의 거리의 최솟값이 -1이라는 것은 방문할 수 있는 손님이 없음을 뜻하므로 -1을 return한다.
기름이 도중에 떨어지는 경우도 마찬가지이다. 목적지까지 잘 도착했으면 운전사의 위치를 이동시키고 손님을 대기열에서 지운다.
실수가 없어지는 그 순간까지 화이팅! 전체 코드를 남기며 마무리하겠다.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Passenger {
int s_r, s_c, d_r, d_c;
Passenger(int _s_r, int _s_c, int _d_r, int _d_c) :s_r(_s_r), s_c(_s_c), d_r(_d_r), d_c(_d_c) {}
};
int N, M, s_r, s_c, d_r, d_c;
int dirR[4] = { 0,1,0,-1 };
int dirC[4] = { 1,0,-1,0 };
int city[21][21];
int visited[21][21];
pair<int, int>driver;
vector<Passenger>passenger;
int Dist(int s_r, int s_c, int d_r, int d_c);
int simulation(int oil);
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int oil;
cin >> N >> M >> oil;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
cin >> city[i][j];
}
}
cin >> driver.first >> driver.second;
for (int i = 0; i < M; i++)
{
cin >> s_r >> s_c >> d_r >> d_c;
passenger.push_back(Passenger(s_r, s_c, d_r, d_c));
}
cout << simulation(oil);
return 0;
}
int Dist(int s_r, int s_c, int d_r, int d_c)
{
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
visited[i][j] = -1;
}
}
queue<pair<int, int>>q;
q.push({ s_r,s_c });
visited[s_r][s_c] = 0;
while (!q.empty())
{
pair<int, int>pos = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int nR = pos.first + dirR[i];
int nC = pos.second + dirC[i];
if (nR > 0 && nR <= N && nC > 0 && nC <= N)
{
if (visited[nR][nC] == -1 && city[nR][nC] == 0)
{
visited[nR][nC] = visited[pos.first][pos.second] + 1;
q.push({ nR ,nC });
}
}
}
}
return visited[d_r][d_c];
}
int simulation(int oil)
{
if (passenger.empty())
{
return oil;
}
int minDistance = Dist(driver.first, driver.second, passenger[0].s_r, passenger[0].s_c);
int p_idx = 0;
for (int i = 1; i < passenger.size(); i++)
{
if (minDistance == -1 || minDistance >= visited[passenger[i].s_r][passenger[i].s_c])
{
if (minDistance == visited[passenger[i].s_r][passenger[i].s_c])
{
if (passenger[p_idx].s_r < passenger[i].s_r || (passenger[p_idx].s_r == passenger[i].s_r && passenger[p_idx].s_c < passenger[i].s_c))
{
continue;
}
}
minDistance = visited[passenger[i].s_r][passenger[i].s_c];
p_idx = i;
}
}
if (minDistance == -1)
{
return -1;
}
oil -= minDistance;
if (oil <= 0)
{
return -1;
}
int cost = Dist(passenger[p_idx].s_r, passenger[p_idx].s_c, passenger[p_idx].d_r, passenger[p_idx].d_c);
if (cost == -1 || oil - cost < 0)
{
return -1;
}
oil += cost;
driver = { passenger[p_idx].d_r,passenger[p_idx].d_c };
passenger.erase(passenger.begin() + p_idx);
return simulation(oil);
}