골드 4문제인데, 정답율은 20퍼가 안된다. 왜일까
vector push_back을 하기 싫어서 미리 선언해놓고 썼다가 sort가 잘못되어서 계속 이상한 결과가 나와서 16%에서 좀 많이 틀렸다 ㅠ.
문제 까다로운 조건은 다 구현해놓고, 초기화를 INT_MAX로 해야하는데, 0으로 잘못해서 계속 틀렸다;
핵심 구현은 BFS + 시뮬레이션 이다.
단, 도달할 수 없는 지점에 고객이 있는 경우 이를 구분할 수 있어야 하며, 최단 거리 고객이 몇 번째 고객인지 등의 정보를 관리해야 하므로 약간 조건이 까다롭다. (풀이 방식은 코드에 주석을 다 적어놔서 코드를 보는게 더 좋을 것 같다)
처음 올바른 제출했을 때 Priority Queue를 이용한 버젼으로 208ms를 기록했다.
최단거리를 찾을 때 PQ를 사용했는데, 굳이 PQ를 쓰지 않아도 될 것 같아서 Queue로 바꿨고, 180ms까지 줄였다(PQ는 push마다 min_heap을 위한 정렬이 필요하기 때문에 queue에 비해 push가 느리다).
그래도 너무 느린 것 같아서 분석을 해봤다.
기존에는 최단거리를 찾을 때, 모든 고객을 for-loop으로 순회하면서 최단거리를 측정했는데, 이를 startInfo 배열에 기록하는 방식으로 바꾸어서 16ms까지 줄였다.
그리고 추가적으로 최단거리 고객이 여러 명일 때, 행과 열을 기준으로 최소의 고객이 선택되는 로직을 모든 고객에 대해서 sort를 한 뒤 정하지 않고, 바로바로 갱신하도록 수정하여서 8ms까지 줄였다.
아무래도 내가 함수랑 구조체를 많이 써서 더 이상 줄이기는 힘들 것 같다(잘하면 4ms까진 줄이겠지만 0ms로 줄이려면 구조체를 줄이고, 함수도 줄여야할듯하다).
코드는 아래와 같다.
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <climits>
#include <cstring>
#include <algorithm>
using namespace std;
typedef struct __pos {
int row;
int col;
int cost;
} pos;
typedef struct __client_info {
pos start;
pos dest;
} client_info;
typedef struct __reach_info {
int idx;
int row;
int col;
int cost;
} reach_info;
typedef struct __shortest_client_info {
int idx;
int cost;
} shortest_client_info;
int n, m, fuel;
int map[22][22];
int visitMap[22][22];
int startInfo[22][22];
pos taxi;
client_info client[411];
int rowDir[4] = { -1, 0, 1, 0 };
int colDir[4] = { 0, 1, 0, -1 };
int global_arrive_cnt;
inline bool is_safe(int row, int col)
{
// 배열을 벗어나는지
if (row < 0 || row > n - 1 || col < 0 || col > n - 1)
return false;
// 가려는 곳에 벽이 있는지
if (map[row][col])
return false;
return true;
}
shortest_client_info get_shortest()
{
// BFS를 위한 visitMap 초기화
for (int i = 0; i < n; i++)
memset(visitMap[i], 0, sizeof(int) * n);
queue<pos> q;
q.push({ taxi.row, taxi.col, 0 });
// BFS 돌면서 고객과의 최단거리를 구함
int arrive_cnt = 0;
reach_info min_reach = { -1, 0, 0, INT_MAX };
while (1) {
if (q.empty())
break;
pos cur = q.front(); q.pop();
if (visitMap[cur.row][cur.col])
continue;
visitMap[cur.row][cur.col] = 1;
// 만약 최단거리를 구해야하는 곳이라면
if (startInfo[cur.row][cur.col]) {
// 문제 조건에 맞는 최단거리 고객을 갱신
if (cur.cost < min_reach.cost)
min_reach = { startInfo[cur.row][cur.col] - 1, cur.row, cur.col, cur.cost };
else if (cur.cost == min_reach.cost) {
if (cur.row < min_reach.row)
min_reach = { startInfo[cur.row][cur.col] - 1, cur.row, cur.col, cur.cost };
else if (cur.row == min_reach.row)
if (cur.col < min_reach.col)
min_reach = { startInfo[cur.row][cur.col] - 1, cur.row, cur.col, cur.cost };
}
arrive_cnt++;
}
// 다 찾았으면 밑의 for-loop을 굳이 진행하지 않고, break해도 됨
if (arrive_cnt == m - global_arrive_cnt)
break;
pos next;
for (int dir = 0; dir < 4; dir++) {
next.row = cur.row + rowDir[dir];
next.col = cur.col + colDir[dir];
if (!is_safe(next.row, next.col))
continue;
next.cost = cur.cost + 1;
q.push(next);
}
}
// 만약 찾아진 고객이 없으면, 택시가 시작 지점에 도달할 수 없는 것이므로 -1을 return
if (arrive_cnt == 0)
return { -1, -1 };
// 그것이 아니라면 찾아진 고객 중 문제 조건에 맞는 최단거리 고객을 반환
shortest_client_info shortest_client = { min_reach.idx, min_reach.cost };
return shortest_client;
}
int go_dest(const shortest_client_info &target)
{
// BFS를 위한 visitMap 초기화
for (int i = 0; i < n; i++)
memset(visitMap[i], 0, sizeof(int) * n);
queue<pos> q;
q.push({ taxi.row, taxi.col, 0 });
// BFS 돌면서 도착지점을 찾음
int cost = -1;
while (1) {
if (q.empty())
break;
pos cur = q.front(); q.pop();
if (visitMap[cur.row][cur.col])
continue;
visitMap[cur.row][cur.col] = 1;
// 만약 해당 고객의 도착지점이라면 break
if (cur.row == client[target.idx].dest.row && cur.col == client[target.idx].dest.col) {
cost = cur.cost;
break;
}
pos next;
for (int dir = 0; dir < 4; dir++) {
next.row = cur.row + rowDir[dir];
next.col = cur.col + colDir[dir];
if (!is_safe(next.row, next.col))
continue;
next.cost = cur.cost + 1;
q.push(next);
}
}
return cost;
}
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> fuel;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> map[i][j];
cin >> taxi.row >> taxi.col;
taxi.row--; taxi.col--;
for (int i = 0; i < m; i++) {
cin >> client[i].start.row >> client[i].start.col >> client[i].dest.row >> client[i].dest.col;
client[i].start.row--; client[i].start.col--;
client[i].dest.row--; client[i].dest.col--;
startInfo[client[i].start.row][client[i].start.col] = i + 1;
}
for (int i = 0; i < m; i++) {
// 최단거리 고객이 몇 번째 고객인지를 찾는다..
shortest_client_info shortest_client = get_shortest();
// 만약 찾아진 고객이 없다면 break (택시가 고객에 도달할 수 없음)
if (shortest_client.idx == -1) {
cout << -1 << "\n";
return 0;
}
// 고객을 찾느라 소모한 연료를 뻄
fuel -= shortest_client.cost;
// 고객과의 거리가 연료보다 크면 break
if (fuel <= 0) {
cout << -1 << "\n";
return 0;
}
// 위 두 if문을 넘겼으면 정상적인 경우이므로 택시 위치를 업데이트
taxi.row = client[shortest_client.idx].start.row;
taxi.col = client[shortest_client.idx].start.col;
// 고객을 도착지점으로 데려다줌
int cost = go_dest(shortest_client);
// 만약 도착지점으로 도착이 불가능하다면 break (벽으로 둘러쌓여있는 등)
if (cost == -1) {
cout << -1 << "\n";
return 0;
}
// 도달하느라 사용한 연료를 뻄
fuel -= cost;
// 만약 도달하는데 필요한 연료가 기존 연료보다 크다면 이는 잘못된 경우이므로 break
if (fuel < 0) {
cout << -1 << "\n";
return 0;
}
// 위 두 if문을 넘겼으면, 연료를 다시 채워줌
fuel += (cost << 1);
// 택시 위치를 다시 업데이트
taxi.row = client[shortest_client.idx].dest.row;
taxi.col = client[shortest_client.idx].dest.col;
global_arrive_cnt++;
// 얘는 이제 최단거리 안구해도 되므로, 0으로 초기화
startInfo[client[shortest_client.idx].start.row][client[shortest_client.idx].start.col] = 0;
}
cout << fuel << "\n";
return 0;
}
내가 보려고 만든 블로그