봄에는 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다. 각각의 나무는 나무가 있는 1×1 크기의 칸에 있는 양분만 먹을 수 있다. 하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다. 만약, 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다.
여름에는 봄에 죽은 나무가 양분으로 변하게 된다. 각각의 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다. 소수점 아래는 버린다.
가을에는 나무가 번식한다. 번식하는 나무는 나이가 5의 배수이어야 하며, 인접한 8개의 칸에 나이가 1인 나무가 생긴다.
겨울에는 S2D2가 땅을 돌아다니면서 땅에 양분을 추가한다. 각 칸에 추가되는 양분의 양은 A[r][c]이고, 입력으로 주어진다.
문제에서 설명한 단계에 맞춰서 똑같이 구현하면 됩니다.
2.접근방법[알고리즘]
구현과 동시에 코드 최적화가 핵심입니다.
시간제한이 0.3초여서 최대한 최적화해야 해결할 수 있습니다.
이 문제에서 한 칸 안에 나무 여러 개가 있을 수 있습니다.
한 칸에 나무가 여러 개 있을 경우 나이가 적은 나무 부터 양분을 섭취해야합니다.
이때 자연스럽게 매번마다 나무를 오름차순으로 sort한 뒤 양분을 섭취하게끔 해야겠다는 생각이 듭니다.
하지만 그러면 시간초과로 틀립니다.
문제 조건 상 sort는 맨 처음 한 번만 해도 풀 수 있습니다.
8칸에 새로 생기는 나무의 나이는 무조건 1이기 때문에
새로 생긴 나무를 맨 앞으로 보내주고
이전에 있던 나무들은 뒤로 보내주면 sort를 해주지 않아도 됩니다.
3.문제풀이코드 C++
#include <bits/stdc++.h>
using namespace std;
int n, m, k, ans, arr[11][11], added[11][11];
int dx[8] = { 1,0,-1,0,1,-1,1,-1 };
int dy[8] = { 0,1,0,-1,1,-1,-1,1 };
struct Tree {
int x, y, age;
bool operator<(const Tree &bb) const {
return age < bb.age;
}
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
vector<Tree> v;
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> added[i][j];
arr[i][j] = 5;
}
}
for (int i = 0; i < m; i++) {
int x, y, z;
cin >> x >> y >> z;
v.push_back({ x,y,z });
}
sort(v.begin(), v.end());
for (int K = 0; K < k; K++) {
vector<Tree> new_v;
// 봄
for (int i = 0; i < v.size(); i++) {
if (v[i].age == 0) continue;
if (v[i].age <= arr[v[i].x][v[i].y]) {
arr[v[i].x][v[i].y] -= v[i].age;
v[i].age++;
// 가을에 새로 생기는 나무들
if (v[i].age % 5 == 0) {
for (int j = 0; j < 8; j++) {
int nx = v[i].x + dx[j];
int ny = v[i].y + dy[j];
//new_v 벡터에 새로생기는 나무들 먼저 넣어줌
if (nx <= 0 || nx > n || ny <= 0 || ny > n)continue;
new_v.push_back({ nx, ny, 1 });
}
}
}
else {
//죽은 나무들
v[i].age = -v[i].age;
}
}
//여름
for (int i = 0; i < v.size(); i++) {
//죽은 나무들 양분으로 전환
if (v[i].age < 0)
{
arr[v[i].x][v[i].y] += (-v[i].age / 2);
}
else {
//new_v에 기존에 있던 나무들 뒤로 보내줌
new_v.push_back(v[i]);
}
}
// 겨울
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
arr[i][j] += added[i][j];
}
}
v.swap(new_v);
}
cout << v.size() << '\n';
return 0;
}
d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우 서쪽을 나타낸다.
로봇 청소기는 다음과 같이 작동한다.
현재 위치를 청소한다.
현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다.
왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
방향을 전환하면서 이동하면서 청소를 할 수 있는 방의 개수를 찾아야 하는 문제다.
2.접근 방법[알고리즘]
이 문제를 DFS를 통해 시뮬레이션을 할 때
종료 조건은 탐색할 수 있는 네 방향 모두 이미 청소되었거나 벽인 경우이고 후진을 할 수 없을 때다.
DFS를 돌면서 네방향 모두 체크해주고,
네방향 모두 이미 청소되었거나 벽이라면
후진을 시켜주고 후진을 할 수 없다면 종료를 시켜준다.
종료조건에 해당하지 않는다면
방향전환을 하고, 방향전환시 전진 했을 때 청소가 가능한 방이라면 전진을 시켜준다.
청소가 불가능 한 방이라면 전진하지 않는다.
해당 좌표가 이미 방문했던 점이라도 다시 방문해도 상관 없다
위 조건에만 만족하면 된다.
DFS코드
void DFS(int x, int y, int d) {
if (ended) return;
bool all_cleaned = true;
//네방향 확인
for (int i = 0; i < 4; i++) {
if (arr[x + dx[i]][y + dy[i]] == 0) {
all_cleaned = false;
break;
}
}
if (all_cleaned) {
// 벽이 있어서 후진 할 수 없다면 종료
if (arr[x - dx[d]][y - dy[d]] == -1) {
ended = true;
return;
}
else {
//후진이 가능할 때
DFS(x - dx[d], y - dy[d], d);
}
}
// 왼쪽으로 방향 회전
int nd = d == 0 ? 3 : d - 1;
int nx = x + dx[nd];
int ny = y + dy[nd];
if (arr[nx][ny] == 0) {
arr[nx][ny] = ++cleaned;
//청소 가능한 방이라면 방향전환후 전진
DFS(nx, ny, nd);
}
else {
//청소 불가능한 방이라면 방향전환만
DFS(x, y, nd);
}
}
3.문제풀이코드 C++
#include <bits/stdc++.h>
using namespace std;
int n, m, r, c, d, arr[51][51], cleaned;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
bool ended = false;
void DFS(int x, int y, int d) {
if (ended) return;
bool all_cleaned = true;
//네방향 확인
for (int i = 0; i < 4; i++) {
if (arr[x + dx[i]][y + dy[i]] == 0) {
all_cleaned = false;
break;
}
}
if (all_cleaned) {
// 벽이 있어서 후진 할 수 없다면 종료
if (arr[x - dx[d]][y - dy[d]] == -1) {
ended = true;
return;
}
else {
//후진이 가능할 때
DFS(x - dx[d], y - dy[d], d);
}
}
// 왼쪽으로 방향 회전
int nd = d == 0 ? 3 : d - 1;
int nx = x + dx[nd];
int ny = y + dy[nd];
if (arr[nx][ny] == 0) {
arr[nx][ny] = ++cleaned;
DFS(nx, ny, nd);
}
else {
DFS(x, y, nd);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
cin >> r >> c >> d;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> arr[i][j];
if (arr[i][j] == 1) {
arr[i][j] = -1;
}
}
}
arr[r][c] = ++cleaned;
DFS(r, c, d);
cout << cleaned;
return 0;
}
명령 1. Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다
명령 2. Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.
동에서 서, 북에서 남으로 회전하는 데는 명령을 두번 해야한다
현재 방향에서 한 번의 명령으로 최대 3칸까지 이동이 가능하다.
벽을 통과할 수는 없다.
2.접근방법[알고리즘]
이 문제는 시작 지점에서 종료 지점 까지 가는데 필요한 최소 명령의 수를 구해야 한다.
한 번의 명령마다 방향전환을 하거나 이동을 한다.
특정 지점을 방문했을 때 단순히 좌표만 저장 하는 게 아니라, 방향에 대한 정보까지 저장을 해주어야한다.
그래서 이전에 방문했는지 체크해주는 배열을 3차원 배열로 만들어
vis[x][y][동 or 서 or 남 or 북] x, y 좌표에 대해서
동, 서, 남 , 북 방향 상태까지 필요햔 명령의 수를 체크해야한다.
하나의 좌표마다 행동할 수 있는 경우의 수는
현재 방향에서 1칸, 2칸, 3칸 이동하기와
현재 방향을 제외한 나머지 방향으로 방향전환 하기가 있다.
한 번의 명령으로 1칸 2칸 3칸 모두 이동하는 게 가능하지만,
방향을 전환 하는데는 동에서 서로 방향을 전환하거나 남에서 북으로 방향을 전환한다면 2번의 명령이 필요하다.
이 때 2번의 명령이 필요한 경우 방향을 전환했다고 바로 방문을 했다고 체크하는 게 아니라
나중에 큐에서 나올 때 체크해주어야한다.
왜냐하면 x,y가 도착지점일 때 x,y에서 방향을 전환하는데 2번 명령을 하는 동안
다른 점에서 한번만에 도착하는 경우도 있기 때문이다.
결과적으로 도착점까지 최소 명령의 수를 구해야하기 때문에 우선순위 큐를 이용했다.
명령의 수를 최소힙으로 계속 pop해주면서 로봇이 최소 명령으로 하는 행동을 먼저하게 한다.
그러다 도착지점에 다다르면 바로 해당 도착지점에 오기까지 필요했던 명령의 수를 바로 리턴해주었다.
우선순위큐를 사용하지 않으면?
만약 우선순위큐를 사용하지 않는다면
도착지점에 도착했다고 바로 리턴해주면 안된다.
방향전환하는데 명령이 2번 일어나는 경우도 있어서
큐에서 뒤에 나오는 경우가 더 적은 명령의 수로 일어나는 행동일 수도 있기 때문이다.
즉 BFS를 돌지만 다른 문제와 다르게 큐에서 뒤에서 나오는 결과가 정답일 수도 있다.
3.문제풀이코드
첫 정답코드
#include <bits/stdc++.h>
using namespace std;
//회전시키는데 명령 1, 현재 방향에서 이동하는데 명령 1,
int n, m, arr[105][105], sx, sy, sd, ex, ey, ed, ans = INT_MAX;
bool vis[105][105][5]; //1동 2서 3남 4북 방향 정보까지 받는다
struct Edge {
int x, y, d, cnt;
Edge(int a, int b, int c, int e) {
x = a;
y = b;
d = c;
cnt = e;
}
bool operator<(const Edge& bb) const {
return cnt > bb.cnt;
}
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
priority_queue<Edge> Q;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> arr[i][j];
}
}
cin >> sx >> sy >> sd;
cin >> ex >> ey >> ed;
vis[sx][sy][sd] = 1;
Q.push(Edge(sx, sy, sd, 0));
while (!Q.empty()) {
int x = Q.top().x;
int y = Q.top().y;
int d = Q.top().d;
int cnt = Q.top().cnt;
Q.pop();
vis[x][y][d] = 1;
//if(d==1)
// cout << x <<' ' << y << " " << "동" << " " << cnt<< '\n';
//else if(d==2)
// cout << x << ' ' << y << " " << "서" << " " << cnt<< '\n';
//else if (d == 3)
// cout << x << ' ' << y << " " << "남" << " " << cnt<< '\n';
//else if (d == 4)
// cout << x << ' ' << y << " " << "북" << " " << cnt<< '\n';
if (x == ex && y == ey && d == ed) {
ans = min(cnt, ans);
}
// 현재 방향에서 이동
// d == 1 : nx : 0 / ny : 1, 2, 3
// d == 2 : nx : 0 / ny : -1, -2, -3;
// d == 3 : nx: 1 , 2 , 3 / ny : 0
// d == 4 : nx : -1 -2 -3 / ny : 0;
if (d == 1) {
for (int i = 1; i <= 3; i++) {
if (y + i > m) break;
if (arr[x][y + i] == 1) break;
if (vis[x][y + i][d] == 0) {
vis[x][y + i][d] = 1;
Q.push(Edge{ x,y + i,d ,cnt + 1 });
}
}
}
else if (d == 2) {
for (int i = 1; i <= 3; i++) {
if (y - i < 1) break;
if (arr[x][y - i] == 1) break;
if (vis[x][y - i][d] == 0) {
vis[x][y - i][d] = 1;
Q.push(Edge{ x,y - i,d ,cnt + 1 });
}
}
}
else if (d == 3) {
for (int i = 1; i <= 3; i++) {
if (x + i > n) break;
if (arr[x + i][y] == 1) break;
if (vis[x + i][y][d] == 0) {
vis[x + i][y][d] = 1;
Q.push(Edge{ x + i,y,d ,cnt + 1 });
}
}
}
else if (d == 4) {
for (int i = 1; i <= 3; i++) {
if (x - i < 1) break;
if (arr[x - i][y] == 1) break;
if (vis[x - i][y][d] == 0) {
vis[x - i][y][d] = 1;
Q.push(Edge{ x - i,y,d ,cnt + 1 });
}
}
}
//방향전환 명령
for (int i = 1; i <= 4; i++) {
if (i == d) continue;
if (vis[x][y][i] == 0) {
if ((d == 1 && i == 2) || (d == 2 && i == 1)) {
Q.push(Edge(x, y, i, cnt + 2));
}
else if ((d == 3 && i == 4) || (d == 4 && i == 3)) {
Q.push(Edge(x, y, i, cnt + 2));
}
else {
vis[x][y][i] = 1;
Q.push(Edge(x, y, i, cnt + 1));
}
}
}
}
cout << ans;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
//회전시키는데 명령 1, 현재 방향에서 이동하는데 명령 1,
int n, m, arr[105][105], sx, sy, sd, ex, ey, ed, ans = INT_MAX;
bool vis[105][105][5]; //1동 2서 3남 4북 방향 정보까지 받는다
struct Edge {
int x, y, d, cnt;
Edge(int a, int b, int c, int e) {
x = a;
y = b;
d = c;
cnt = e;
}
bool operator<(const Edge& bb) const {
return cnt > bb.cnt;
}
};
priority_queue<Edge> Q;
void move(int x, int y, int d, int cnt) {
if (d == 1) {
for (int i = 1; i <= 3; i++) {
if (y + i > m) break;
if (arr[x][y + i] == 1) break;
if (vis[x][y + i][d] == 0) {
vis[x][y + i][d] = 1;
Q.push(Edge{ x,y + i,d ,cnt + 1 });
}
}
}
else if (d == 2) {
for (int i = 1; i <= 3; i++) {
if (y - i < 1) break;
if (arr[x][y - i] == 1) break;
if (vis[x][y - i][d] == 0) {
vis[x][y - i][d] = 1;
Q.push(Edge{ x,y - i,d ,cnt + 1 });
}
}
}
else if (d == 3) {
for (int i = 1; i <= 3; i++) {
if (x + i > n) break;
if (arr[x + i][y] == 1) break;
if (vis[x + i][y][d] == 0) {
vis[x + i][y][d] = 1;
Q.push(Edge{ x + i,y,d ,cnt + 1 });
}
}
}
else if (d == 4) {
for (int i = 1; i <= 3; i++) {
if (x - i < 1) break;
if (arr[x - i][y] == 1) break;
if (vis[x - i][y][d] == 0) {
vis[x - i][y][d] = 1;
Q.push(Edge{ x - i,y,d ,cnt + 1 });
}
}
}
}
void turn_dir(int x, int y, int d, int cnt) {
for (int i = 1; i <= 4; i++) {
if (i == d) continue;
if (vis[x][y][i] == 0) {
if ((d == 1 && i == 2) || (d == 2 && i == 1)) {
// 바로 방문 체크를 하면 안된다. 방향전환 하는 동안 먼저 방문하는 경우가 있을 수도 있다.
Q.push(Edge(x, y, i, cnt + 2));
}
else if ((d == 3 && i == 4) || (d == 4 && i == 3)) {
Q.push(Edge(x, y, i, cnt + 2));
}
else {
vis[x][y][i] = 1;
Q.push(Edge(x, y, i, cnt + 1));
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
//입력
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> arr[i][j];
}
}
cin >> sx >> sy >> sd;
cin >> ex >> ey >> ed;
vis[sx][sy][sd] = 1;
Q.push(Edge(sx, sy, sd, 0));
while (!Q.empty()) {
int x = Q.top().x;
int y = Q.top().y;
int d = Q.top().d;
int cnt = Q.top().cnt;
Q.pop();
vis[x][y][d] = 1;
if (x == ex && y == ey && d == ed) {
cout << cnt;
return 0;
}
// 현재 방향에서 이동
move(x, y, d, cnt);
//방향전환 명령
turn_dir(x,y,d,cnt);
}
return 0;
}
각각의 큐를 만들고 시간을 증가시키면서 새로 방문한 노드에 대해서 일괄적으로 상하좌우 탐색한다.
고슴도치는 물이 방문할 점을 방문할 수 없기 때문에
물 -> 고슴도치 -> 물 -> 고슴도치 순으로 BFS를 돈다.
3.문제풀이코드 C++
#include <bits/stdc++.h>
using namespace std;
int r, c;
char arr[53][53];
bool s_check[53][53], wt_check[53][53];
int ch[53][53];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
//물 먼저 이동 후 고슴도치 이동
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> r >> c;
queue<pair<int, int> > wt;
queue<pair<int, int> > s;
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
cin >> arr[i][j];
if (arr[i][j] == '*') {
ch[i][j] = -1;
wt.push({ i,j });
wt_check[i][j] = 1;
}
else if (arr[i][j] == 'S') {
ch[i][j] = 1;
s.push({ i,j });
s_check[i][j] = 1;
}
else if (arr[i][j] == 'X') {
ch[i][j] = 2;
}
else if (arr[i][j] == 'D') {
ch[i][j] = 3;
}
}
}
int t = 0;
while (true) {
int s_size = s.size();
int wt_size = wt.size();
if (s_size == 0) break;
for (int i = 0; i < wt_size; i++) {
int x = wt.front().first;
int y = wt.front().second;
wt.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx <= 0 || nx > r || ny <= 0 || ny > c||wt_check[nx][ny] == 1) continue;
if (ch[nx][ny] == 0 || ch[nx][ny]==1) {
wt_check[nx][ny] = 1;
ch[nx][ny] = -1;
wt.push({ nx,ny });
}
}
}
for (int i = 0; i < s_size; i++) {
int x = s.front().first;
int y = s.front().second;
s.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx <= 0 || nx > r || ny <= 0 || ny > c || s_check[nx][ny] == 1) continue;
if (ch[nx][ny] == 0 || ch[nx][ny] == 1 ) {
ch[nx][ny] = 1;
s_check[nx][ny] = 1;
s.push({ nx,ny });
}
else if (ch[nx][ny] == 3) {
cout << t+1;
return 0;
}
}
}
t++;
//print();
}
cout << "KAKTUS" << '\n';
return 0;
}
백준 3055번 탈출 메모리 시간
틀린이유
처음에 고슴도치와 물이 방문한 좌표를 체크해주지 않아 틀렸다
BFS든 DFS든 방문해준 점을 체크표시해주지 않으면 방문한 곳을 계속 방문해서 무한 루프에 빠지고 만다.
