Problem 문제풀이
청소년 상어에 이어 어른 상어를 풀어보았다.
상어소리만 들어도 노이로제 걸릴 것 같다는 당신! 상어랑 친해져 보라.
가까이서 보면 귀여운 친구이다. 각설하고
전략
-
상어들의 정보를 저장하는 배열과 바다의 정보를 저장하는 배열이 필요하다.
-
시간을 증가시키면서 상어들을 움직인다.
-
상어를 움직일 때 두 가지 상황을 주의하자.
-
동시에 한 장소로 상어가 몰린 경우
-
내가 가려하는 곳에 다른 상어의 냄새가 날 경우
-
-
3-1의 경우 늦게 온 상어가 죽으면 된다.
말넘심 -
3-2의 경우 우선순위에 따라 이동하자.
-
2~5를 반복한다.
-
1번 상어만 남았거나 timer가 1000을 넘겼을 경우 simulation을 종료한다.
문제를 풀 수록 계획을 세우는 시간이 길어지고 있다. 매우 좋은 현상이라 생각한다.
먼저 상어와 바다의 정보를 저장할 struct를 만들어보자.
struct Ocean {
int time;
int smell;
Ocean() {}
Ocean(int _time, int _smell):time(_time),smell(_smell){}
};
struct Shark {
int row;
int col;
int dir;
Shark() {}
Shark(int _row, int _col, int _dir) :row(_row), col(_col), dir(_dir) {}
};
Shark shark[401];
Ocean ocean[2][21][21];
Ocean이 [21][21]이 아닌 [2][21][21]배열인 이유는 이동 전, 이동 후의 바다의 상태를 저장하기 위해서이다.
이제 상어를 이동시키는 함수를 만들어보자.
for (int i = 1; i <= M; i++)
{
if (shark[i].row == -1 && shark[i].col == -1)
{
continue;
}
bool isMoved = false;
for (int j = 0; j < 4; j++)
{
int nR = shark[i].row + dirR[priority[i][shark[i].dir-1][j]];
int nC = shark[i].col + dirC[priority[i][shark[i].dir-1][j]];
if ((nR >= 0 && nR < N && nC >= 0 && nC < N) && (ocean[timer % 2][nR][nC].smell == 0))
{
if (ocean[(timer + 1) % 2][nR][nC].smell > 0)
{
shark[i].row = -1;
shark[i].col = -1;
}
else
{
shark[i].row = nR;
shark[i].col = nC;
shark[i].dir = priority[i][shark[i].dir - 1][j];
ocean[(timer + 1) % 2][nR][nC].smell = i;
ocean[(timer + 1) % 2][nR][nC].time = K+1;
}
isMoved = true;
break;
}
}
if (isMoved)
{
continue;
}
이동 전 바다 ocean[timer%2]에서 아무 냄새가 나지 않을 때 이동을 시킨다.
그런데 이동을 하려던 차! 이동 후 바다 ocean[(timer+1)%2]에서 냄새가 난다!!! 나보다 먼저 온 손님이 있는 것이다.
이 경우 조용히 죽으면 된다. R.I.P 죽었건 살았건 i번째 상어가 무사히(?) 이동했으면 차례를 넘긴다.
그러나 이동을 하지 못한 상어들도 분명 있을 것이다. 이 경우를 살펴보자.
for (int j = 0; j < 4; j++)
{
int nR = shark[i].row + dirR[priority[i][shark[i].dir-1][j]];
int nC = shark[i].col + dirC[priority[i][shark[i].dir-1][j]];
if ((nR >= 0 && nR < N && nC >= 0 && nC < N) && (ocean[timer % 2][nR][nC].smell == i))
{
if (ocean[(timer + 1) % 2][nR][nC].smell != i)
{
shark[i].row = -1;
shark[i].col = -1;
}
else
{
shark[i].row = nR;
shark[i].col = nC;
shark[i].dir = priority[i][shark[i].dir - 1][j];
ocean[(timer + 1) % 2][nR][nC].smell = i;
ocean[(timer + 1) % 2][nR][nC].time = K+1;
}
break;
}
}
}
인덱스에 매우매우매우 주의하자. 정 헷갈리면 변수를 더 선언해서라도 틀리지 않는 것을 추천한다.
이제 Step 6까지 완료했다. 나머지는 timer만 동작하게 하면 끝이다.
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (ocean[(timer + 1) % 2][i][j].time > 0)
{
ocean[(timer + 1) % 2][i][j].time--;
if (ocean[(timer + 1) % 2][i][j].time == 0)
{
ocean[(timer + 1) % 2][i][j].smell = 0;
}
}
}
}
timer++;
return simulation();
아기, 청소년, 어른 상어까지 헤치웠다. 설마 노인 상어는 안 나오겠지?ㅋㅋㅋㅋㅋㅋㅋㅋ
전체 코드를 남기며 마무리하겠다. Good Luck!
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <tuple>
using namespace std;
struct Ocean {
int time;
int smell;
Ocean() {}
Ocean(int _time, int _smell):time(_time),smell(_smell){}
};
struct Shark {
int row;
int col;
int dir;
Shark() {}
Shark(int _row, int _col, int _dir) :row(_row), col(_col), dir(_dir) {}
};
int N, M, K, tmp, timer;
Shark shark[401];
int priority[401][4][4]; // 상어의 번호, 상하좌우 우선순위, 각각의 우선순위
Ocean ocean[2][21][21];
int dirR[5] = { 0,-1,1,0,0 };
int dirC[5] = { 0,0,0,-1,1 };
int simulation();
bool check();
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M >> K;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> tmp;
if (tmp > 0)
{
ocean[0][i][j] = Ocean(K, tmp);
shark[tmp] = Shark(i,j,0);
}
else
{
ocean[0][i][j] = Ocean(0, 0);
}
}
}
for (int i = 1; i <= M; i++) // 1 : 상, 2 : 하, 3 : 좌, 4 : 우
{
cin >> tmp;
shark[i].dir = tmp;
}
for (int i = 1; i <= M; i++)
{
for (int j = 0; j < 4; j++)
{
for (int k = 0; k < 4; k++)
{
cin >> priority[i][j][k];
}
}
}
cout << simulation();
return 0;
}
int simulation()
{
if (timer > 1000)
{
return -1;
}
if (check())
{
return timer;
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
ocean[(timer + 1) % 2][i][j] = ocean[timer % 2][i][j];
}
}
/*cout << endl;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (ocean[timer % 2][i][j].time == K)
{
cout << shark[ocean[timer % 2][i][j].smell].dir << ' ';
}
cout << "{" << ocean[timer % 2][i][j].smell << ":" << ocean[timer % 2][i][j].time << "}\t";
}
cout << endl;
}
cout << endl;*/
for (int i = 1; i <= M; i++)
{
if (shark[i].row == -1 && shark[i].col == -1)
{
continue;
}
bool isMoved = false;
for (int j = 0; j < 4; j++)
{
int nR = shark[i].row + dirR[priority[i][shark[i].dir-1][j]];
int nC = shark[i].col + dirC[priority[i][shark[i].dir-1][j]];
if ((nR >= 0 && nR < N && nC >= 0 && nC < N) && (ocean[timer % 2][nR][nC].smell == 0))
{
if (ocean[(timer + 1) % 2][nR][nC].smell > 0)
{
shark[i].row = -1;
shark[i].col = -1;
}
else
{
shark[i].row = nR;
shark[i].col = nC;
shark[i].dir = priority[i][shark[i].dir - 1][j];
ocean[(timer + 1) % 2][nR][nC].smell = i;
ocean[(timer + 1) % 2][nR][nC].time = K+1;
}
isMoved = true;
break;
}
}
if (isMoved)
{
continue;
}
for (int j = 0; j < 4; j++)
{
int nR = shark[i].row + dirR[priority[i][shark[i].dir-1][j]];
int nC = shark[i].col + dirC[priority[i][shark[i].dir-1][j]];
if ((nR >= 0 && nR < N && nC >= 0 && nC < N) && (ocean[timer % 2][nR][nC].smell == i))
{
if (ocean[(timer + 1) % 2][nR][nC].smell != i)
{
shark[i].row = -1;
shark[i].col = -1;
}
else
{
shark[i].row = nR;
shark[i].col = nC;
shark[i].dir = priority[i][shark[i].dir - 1][j];
ocean[(timer + 1) % 2][nR][nC].smell = i;
ocean[(timer + 1) % 2][nR][nC].time = K+1;
}
break;
}
}
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (ocean[(timer + 1) % 2][i][j].time > 0)
{
ocean[(timer + 1) % 2][i][j].time--;
if (ocean[(timer + 1) % 2][i][j].time == 0)
{
ocean[(timer + 1) % 2][i][j].smell = 0;
}
}
}
}
timer++;
return simulation();
}
bool check()
{
for (int i = 2; i <= M; i++)
{
if (shark[i].row == -1 && shark[i].col == -1)
{
continue;
}
else
{
return false;
}
}
return true;
}