그리고, 여름에 나무의 삭제가 발생할 때, 삭제되는 나무에 대한 처리를 할 때, 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;
}
이를 통해서 다른섬이 만났을 때, 그 지점까지의 거리가 만들 수 있는 다리의 최소 거리인지 판단해준다.
#include<iostream>
#include<queue>
using namespace std;
int m[100][100], n, dis[100][100], idx[100][100];
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
int Min = -2;
queue <pair<int, int> > q;
void init() {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
dis[i][j] = -1;
while (!q.empty()) q.pop();
}
void minCal(int val) { //최소 거리인지 판단
if (Min == -2) { //최솟값이 갱신된 적이 없다면
Min = val;
return;
}
else {
if (Min > val) Min = val;
else
return;
}
}
bool boundCheck(int r, int c) {
return r < 0 || c < 0 || r >= n || c >= n;
}
void dfs(int row, int col, int landCnt) {
dis[row][col]++;
idx[row][col] = landCnt; //섬의 index 지정
for (int i = 0; i < 4; i++) {
int nr = row + dr[i];
int nc = col + dc[i];
if (boundCheck(nr, nc) || m[nr][nc] == 0 || dis[nr][nc] >= 0) continue;
dfs(nr, nc, landCnt);
}
}
void bfs(pair<int, int> start) {
q.push(start);
dis[start.first][start.second]++;
while (!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nr = cur.first + dr[i];
int nc = cur.second + dc[i];
if (boundCheck(nr, nc) || dis[nr][nc] >= 0) continue;
if (m[nr][nc] == 1) {
//섬을 만났을 때
if (idx[nr][nc] == idx[cur.first][cur.second]) continue;
else {
//출발한 섬과 다른 섬을 만났을 때
minCal(dis[cur.first][cur.second]);
init();
return;
}
}
q.push({ nr, nc });
dis[nr][nc] = dis[cur.first][cur.second] + 1;
idx[nr][nc] = idx[cur.first][cur.second];
//어느 섬에서 측정한 거리라는 것을 명시
}
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> m[i][j];
init();
int landCnt = 0; // 섬 번호
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dis[i][j] < 0 && m[i][j] == 1) {
landCnt++;
dfs(i, j, landCnt);
}
}
}
init(); //방문처리 배열 초기화
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dis[i][j] < 0 && m[i][j] == 1) {
bfs({ i, j });
}
}
}
cout << Min << '\n';
return 0;
}
//섬과 섬을 잇는 가장 짧은 다리
//1에서 시작해서 0으로 퍼져나가게
//퍼져나가기 시작한 점이 어느 섬인지 확인하면서 비교
//dfs로 섬 개수 파악하고 번호 매김
//섬이면서 방문 안 한 곳 bfs -> 주변이 바다인 곳 방문(거리측정)
//가다가 섬이면서 내 섬이 아닌 곳을 만나면 중지 -> 길이 최소 비교