그리고, 여름에 나무의 삭제가 발생할 때, 삭제되는 나무에 대한 처리를 할 때, vector.erase를 사용하고, 삭제되는 나무들에 대한 정보를 큐로 옮긴 이후에, 큐에서 pop하면서 처리를 해서 시간초과를 받았다.
이를 해결하기위해서, 봄에 땅으로부터 영양분을 흡수하는 것은 어짜피 나무가 나이로 정렬된 상태로 이루어지고, 특정 나이가 땅의 양분보다 많은 순간이 온다면, 그 나무보다 나이가 많은 나무들은 자연스럽게 확인할 가치가 없어지기 때문에, 봄에 영양분을 흡수했던 나무들을 임시 벡터에 넣어두고, 실패지점 이후에 원본 벡터를 clear한 이후에, 임시 벡터에 들어있는 데이터를 원래 벡터에 옮겨주면 여름에 대한 구현을 할 수 있다.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll grd[11][11];
int igr[11][11], n, m, k;
vector<ll> v[11][11];
int dr[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dc[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
int main(void) {
//1-indexed
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> igr[i][j];
grd[i][j] = 5;
}
}
for (int i = 1; i <= m; i++) {
int r, c, age;
cin >> r >> c >> age;
v[r][c].push_back(age);
}
for (int i = 1; i <= k; i++) {
//봄
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (v[i][j].size() > 0) { //i행 j열에 나무가 존재하면
vector<ll> tmp;
sort(v[i][j].begin(), v[i][j].end()); //어린 나무부터
//땅양분이 나이보다 많으면 나이 증가, 땅 양분 감소
ll dead = 0;
for (int t = 0; t < v[i][j].size(); t++) {
if (v[i][j][t] <= grd[i][j]) {
tmp.push_back(v[i][j][t] + 1);
grd[i][j] -= v[i][j][t];
}
else {
dead += v[i][j][t] / 2;
}
}
//여름
v[i][j].clear();
v[i][j] = tmp;
grd[i][j] += dead;
}
}
}
//가을
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (v[i][j].size() > 0) {
for (int t = 0; t < v[i][j].size(); t++) {
if (v[i][j][t] % 5 == 0) {
for (int ii = 0; ii < 8; ii++) {
int nr = i + dr[ii];
int nc = j + dc[ii];
if (nr < 1 || nc < 1 || nr > n || nc > n) continue;
v[nr][nc].push_back(1);
}
}
}
}
}
}
//겨울
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
grd[i][j] += igr[i][j];
}
}
}
ll cnt = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (v[i][j].size() > 0) cnt += v[i][j].size();
}
}
cout << cnt;
return 0;
}
다리의 경우, 지금 버티고 있는 무게가 몇인지 그리고 현재 다리 위에 몇 개의 트럭이 올라와 있는지를 항상 유지해야 한다.
트럭의 경우에는, 각 트럭 별로 트럭의 무게, 그리고 다리 위에 있는지 여부, 그리고 다리 위에 존재한 시간(혹은 거리)을 유지해야 한다.
따라서 위와 같은 조건을 나타내기 위해서 구조체를 사용했다.
무한 루프를 만들고, 마지막 차가 다리를 탈출하는 순간을 루프 탈출 조건으로 잡았다.
#include<iostream>
using namespace std;
struct Bridge {
int wei = 0; //다리에 가해진 무게
int cnt = 0; //다리위 차의 개수
};
struct Car {
int wei = 0; //차의 무게
int time = 0;//차의 이동 시간(거리)
bool onBri = false; //차가 다리위에 있는지 여부
};
Car car[2000];
Bridge brg;
int n, len, lim; //차의 개수, 다리의 길이, 하중 제한
int main(void) {
cin >> n >> len >> lim;
for (int i = 0; i < n; i++)
cin >> car[i].wei;
brg.cnt = 0;
brg.wei = 0;
int idx = 0, Time = 0; //다리위에 올라가는 차의 인덱스, 전체 시간
bool endFlag = false;
while (1) {
//다리 위의 차들 이동(시간 증가)
for (int i = 0; i < n; i++) {
if (car[i].onBri) {
car[i].time++;
//printf("%d번 차 움직인 거리: %d\n", i, car[i].time);
if (car[i].time >= len) {
if (i == n - 1) {
//다리를 벗어나는 차가 마지막 차라면
endFlag = true;
Time++;
break;
}
//이 차가 다리를 다 건너면
brg.cnt--;
brg.wei = brg.wei - car[i].wei;
car[i].onBri = false;
}
}
}
if (endFlag) break;
if (lim - brg.wei >= car[idx].wei && brg.cnt < len) {
//가능한 무게이면서 다리위에 공간이 남았으면
car[idx].onBri = true;
brg.wei = brg.wei + car[idx].wei;
idx++;
brg.cnt++;
}
Time++;
}
cout << Time << '\n';
return 0;
}
움직임 배열을 입력받는 U와 D로 정해주고, 시작점을 큐에 넣은 이후에, 하나씩 pop 해서 확인해주면 된다.
#include<iostream>
#include<queue>
using namespace std;
int n, src, des, Up, Down;
int dis[1000001]; //1 indexed
int Move[2];
queue<int> q;
void bfs(int start) {
q.push(start);
dis[start]++;
while (!q.empty()) {
int cur = q.front();
q.pop();
for (int i = 0; i < 2; i++) {
int nf = cur + Move[i];
if (nf < 1 || nf > n || dis[nf] >= 0) continue;
q.push(nf);
dis[nf] = dis[cur] + 1;
}
}
}
int main(void) {
cin >> n >> src >> des >> Up >> Down;
for (int i = 1; i <= n; i++)
dis[i] = -1;
Move[0] = Up;
Move[1] = Down * -1;
bfs(src);
if (dis[des] == -1) cout << "use the stairs\n";
else
cout << dis[des] << '\n';
return 0;
}