📌1차 실패 : 붙어서 시작할때와 아닐때를 구별해야 함!
#include <iostream>
#include <cstring>
#include <vector>
#define MAX_MAP_SIZE 105
using namespace std;
struct Germ {
int row, col, dis, dir, size;
};
int n, m, k;
vector<Germ> germ;
// Germ map[MAX_MAP_SIZE][MAX_MAP_SIZE];
int answer;
// 위, 아래, 오른쪽, 왼쪽
int dr[] = { 0, -1, 1, 0, 0 };
int dc[] = { 0, 0, 0, 1, -1 };
void CLEAR()
{
n = m = k = 0;
germ.clear();
// memset(map, 0, sizeof(map));
answer = 0;
}
void INPUT()
{
cin >> n >> m >> k;
for (int i = 0; i < k; i++)
{
int row, col, s, d, b;
cin >> row >> col >> s >> d >> b;
// map[row][col] = { s, d, b };
germ.push_back({ row, col, s, d, b });
}
}
int changeDir(int dir)
{
if (dir == 1)
return 2;
else if (dir == 2)
return 1;
else if (dir == 3)
return 4;
else if (dir == 4)
return 3;
}
void germSearch(int col)
{
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < germ.size(); j++)
{
// 곰팡이 채취
if (germ[j].row == i && germ[j].col == col)
{
answer += germ[j].size;
germ.erase(germ.begin() + j);
return;
}
}
}
}
void germMove()
{
for (int i = 0; i < germ.size(); i++)
{
for (int j = 1; j <= germ[i].dis; j++)
{
int nextRow = germ[i].row + dr[germ[i].dir];
int nextCol = germ[i].col + dc[germ[i].dir];
if (nextRow == 1 || nextCol == 1 || nextRow >= n || nextCol >= m)
{
germ[i].dir = changeDir(germ[i].dir);
nextRow += dr[germ[i].dir];
nextCol += dc[germ[i].dir];
}
else if (nextRow == 0 || nextCol == 0)
{
germ[i].dir = changeDir(germ[i].dir);
nextRow += dr[germ[i].dir];
nextCol += dc[germ[i].dir];
}
else {
germ[i].row = nextRow;
germ[i].col = nextCol;
}
}
int debug = 0;
}
}
void germDevour()
{
}
void SOLVE()
{
int debug = 0;
for (int col = 1; col <= m; col++)
{
germSearch(col);
germMove();
germDevour();
}
cout << answer << endl;
}
int main()
{
CLEAR();
INPUT();
SOLVE();
return 0;
} 📌2차 실패
✔️ 문제에서 시간복잡도가 발생할 수 있는 요소들을 제거해야 함
=>
speed가 1...10000이므로 시간초과 발생
=>
2N-2마다 제자리로 온다는 것을 이용해 "최적화"
✔️ 하나의 동작은 하나의 함수로 구현
=>
예를 들어, "곰팡이를 찾는다", "곰팡이가 이동한다"는 따로 구현되어야 함
=>
또한, "좌표"의 이동이 곧 "곰팡이"의 이동일 필요는 없음.
Input과 Output을 명확히 나누어야 함.
✔️ 현재 MAP 과 다음 시간에서의 NEW_MAP의 사용을 우선고려하기!
=> 절대적이어야 하는 MAP이 탐색과정에서 변하면 "디버깅하기 어려운" 오류가 발생
=> "탐색"과 "절대상태"를 분리해서 고려해야함!!
✔️ 왜 틀렸는지는 모르겠음... 🤣
#include <iostream>
#include <cstring>
#define MAX_MAP 105
using namespace std;
struct Germ {
int speed;
int dir;
int size;
};
int N, M, K;
Germ MAP[MAX_MAP][MAX_MAP];
// 문제 : 0이 아닐때 이동하기때문에 이동하고나면 삭제해야함
// 비교가 일어나는 시점은 이동이 끝났을 때
Germ NEXT[MAX_MAP][MAX_MAP];
// 경로를 지우면서 가는 문제
Germ TEMP[MAX_MAP][MAX_MAP];
// 위, 아래, 오른쪽, 왼쪽
int dr[] = { 0, -1, 1, 0, 0 };
int dc[] = { 0, 0, 0, 1, -1 };
// 정답
int answer;
void mapcopy()
{
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= M; j++)
{
MAP[i][j] = NEXT[i][j];
NEXT[i][j] = { 0, 0, 0 };
}
}
}
int isCrashed(int r, int c, int& d)
{
// 위에서 충돌
if (r == 1 && d == 1)
{
d = 2;
return 2;
}
// 아래서 충돌
else if (r == N && d == 2)
{
d = 1;
return 1;
}
// 왼쪽 충돌
else if (c == 1 && d == 4)
{
d = 3;
return 3;
}
// 오른쪽 충돌
else if (c == M && d == 3)
{
d = 4;
return 4;
}
// 충돌 안함
else
return 0;
}
//int changeDir(int dir) {
// if (dir == 1)
// return 2;
// else if (dir == 2)
// return 1;
// else if (dir == 3)
// return 4;
// else if (dir == 4)
// return 3;
//}
void move()
{
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= M; c++)
{
// 곰팡이를 찾으면
if (MAP[r][c].size != 0)
{
// memset(TEMP, 0, sizeof(TEMP));
int now_speed = MAP[r][c].speed;
int now_size = MAP[r][c].size;
int now_r = r;
int now_c = c;
TEMP[r][c] = MAP[r][c];
// 속도만큼 이동
if (now_speed == 0)
{
NEXT[r][c] = { MAP[r][c] };
// MAP[r][c] = { 0, 0, 0 };
}
for (int s = 0; s < now_speed; s++)
{
// 벽에 도달하면 방향을 바꾸고 속력을 유지
if (isCrashed(now_r, now_c, TEMP[now_r][now_c].dir))
{
s -= 1;
continue;
}
int nr = now_r + dr[TEMP[now_r][now_c].dir];
int nc = now_c + dc[TEMP[now_r][now_c].dir];
// 이동을 "끝낸" 후 곰팡이가 있으면 경쟁 => NEXT와 비교
if (s == now_speed - 1 && NEXT[nr][nc].size != 0)
{
if (now_size < NEXT[nr][nc].size) {
// NEXT[nr][nc] = { NEXT[nr][nc] };
// MAP[r][c] = { 0, 0, 0 };
TEMP[now_r][now_c] = { 0, 0, 0 };
TEMP[r][c] = { 0, 0, 0 };
}
else {
NEXT[nr][nc] = { TEMP[now_r][now_c] };
// MAP[r][c] = { 0, 0, 0 };
TEMP[now_r][now_c] = { 0, 0, 0 };
TEMP[r][c] = { 0, 0, 0 };
}
}
// 이동을 "끝낸" 후 경쟁 곰팡이가 없으면
else if (s == now_speed - 1) {
NEXT[nr][nc] = { TEMP[now_r][now_c] };
// MAP[r][c] = { 0, 0, 0 };
TEMP[now_r][now_c] = { 0, 0, 0 };
TEMP[r][c] = { 0, 0, 0 };
}
// 한 칸 이동
else {
TEMP[nr][nc] = { TEMP[now_r][now_c] };
TEMP[now_r][now_c] = { 0, 0, 0 };
now_r = nr;
now_c = nc;
}
}
}
}
}
// 이동 끝나면 NEXT -> MAP으로 이동
mapcopy();
}
void search(int c)
{
for (int r = 1; r <= N; r++)
{
// 곰팡이를 찾으면
if (MAP[r][c].size != 0)
{
answer += MAP[r][c].size;
MAP[r][c] = { 0, 0, 0 };
return;
}
}
}
void CLEAR()
{
memset(MAP, 0, sizeof(MAP));
answer = 0;
}
void INPUT()
{
cin >> N >> M >> K;
for (int i = 0; i < K; i++)
{
int x, y, s, d, b;
cin >> x >> y >> s >> d >> b;
if (d == 1 || d == 2) {
s = s % (2 * N - 2);
}
else {
s = s % (2 * M - 2);
}
MAP[x][y] = { s, d, b };
}
}
void SOLVE()
{
// 첫번째 열부터
for (int c = 1; c <= M; c++)
{
// 탐색
search(c);
// 이동
move();
// 디버깅
int debug = 0;
}
cout << answer << endl;
}
int main()
{
CLEAR();
INPUT();
SOLVE();
return 0;
}📌 풀이 완료!!!
#include <iostream>
#include <cstring>
#define MAX_MAP 105
using namespace std;
struct Germ {
int speed;
int dir;
int size;
};
int N, M, K;
Germ MAP[MAX_MAP][MAX_MAP];
// 문제 : 0이 아닐때 이동하기때문에 이동하고나면 삭제해야함
// 비교가 일어나는 시점은 이동이 끝났을 때
Germ NEW[MAX_MAP][MAX_MAP];
// 위, 아래, 오른쪽, 왼쪽
int dr[] = { 0, -1, 1, 0, 0 };
int dc[] = { 0, 0, 0, 1, -1 };
// 정답
int answer;
void mapcopy()
{
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= M; j++)
{
MAP[i][j] = NEW[i][j];
NEW[i][j] = { 0, 0, 0 };
}
}
}
int isCrashed(int r, int c, int& d)
{
// 위에서 충돌
if (r == 1 && d == 1)
{
d = 2;
return 2;
}
// 아래서 충돌
else if (r == N && d == 2)
{
d = 1;
return 1;
}
// 왼쪽 충돌
else if (c == 1 && d == 4)
{
d = 3;
return 3;
}
// 오른쪽 충돌
else if (c == M && d == 3)
{
d = 4;
return 4;
}
// 충돌 안함
else
return 0;
}
void getNextPos(Germ &g, int &r, int &c)
{
int nr = r;
int nc = c;
for (int s = 0; s < g.speed; s++)
{
if (isCrashed(nr, nc, g.dir))
{
s -= 1;
continue;
}
else
{
nr += dr[g.dir];
nc += dc[g.dir];
}
}
r = nr;
c = nc;
}
void move()
{
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= M; j++)
{
if (MAP[i][j].size != 0)
{
int nextRow = i;
int nextCol = j;
getNextPos(MAP[i][j], nextRow, nextCol);
// 이동이 끝난 후 곰팡이 크기 비교
if (NEW[nextRow][nextCol].size != 0)
{
if (MAP[i][j].size > NEW[nextRow][nextCol].size)
{
NEW[nextRow][nextCol] = MAP[i][j];
}
}
else
{
NEW[nextRow][nextCol] = MAP[i][j];
}
}
}
}
mapcopy();
}
void search(int c)
{
for (int r = 1; r <= N; r++)
{
// 곰팡이를 찾으면
if (MAP[r][c].size != 0)
{
answer += MAP[r][c].size;
MAP[r][c] = { 0, 0, 0 };
return;
}
}
}
void CLEAR()
{
memset(MAP, 0, sizeof(MAP));
answer = 0;
}
void INPUT()
{
cin >> N >> M >> K;
for (int i = 0; i < K; i++)
{
int x, y, s, d, b;
cin >> x >> y >> s >> d >> b;
// speed가 1~10000이므로 코드 최적화
if (d == 1 || d == 2) {
s = s % (2 * N - 2);
}
else {
s = s % (2 * M - 2);
}
MAP[x][y] = { s, d, b };
}
}
void SOLVE()
{
// 첫번째 열부터
for (int c = 1; c <= M; c++)
{
// 탐색
search(c);
// 이동
move();
// 디버깅
int debug = 0;
}
cout << answer << endl;
}
int main()
{
CLEAR();
INPUT();
SOLVE();
return 0;
}
공부방