백준 23290번 : 마법사상어와 복제

sol : 118' 21''

• 수행 시간 : 88ms -> 0ms
• 메모리 : 47092KB -> 2028KB

Learnings

• 이번엔 CanGo 함수를 사용해서 좀 더 깔끔하게 짜보려 했는데, 여기서 마지막에 return을 선언해주지 않아 오류 코너 케이스가 발생했다.
• 물고기 정보는 굳이 아이디까지 관리할 필요가 없었다. 현재 발생하는 가장 큰 병목은 매번 상어가 물고기를 먹을 때마다 fishes를 전수조사한다는 점이다.
• fishGrid를 선언하여 각 셀을 vector로 만들고, 물고기의 방향만 넣는 식으로 관리한다면 훨씬 간단하게 만들 수 있다.

개선 전

#include <iostream>
#include <vector>
#include <utility>
#include <tuple>

using namespace std;

#define MAX_N 5
#define EMPTY 0
#define CANT_MOVE 8

int m, s;
int turn;
// 좌, 상좌, 상, 상우, 우, 하우, 하, 하좌
const int ds[9][2] = { {0, 0}, { 0, -1 }, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1} };
// 상, 좌, 하, 우
const int sds[4][2] = { {-1, 0}, {0, -1}, {1, 0}, {0, 1} };
// 냄새를 기록하는 그리드
int markGrid[MAX_N][MAX_N];
// 물고기의 수를 기록하는 그리드
int fishNumGrid[MAX_N][MAX_N];
// 복제될 물고기의 수를 기록하는 그리드
int dupGrid[MAX_N][MAX_N];

// 위치, 방향, 생존
struct Fish {
	int i;
	int j;
	int dir;
	bool dead;

	Fish() : i(-1), j(-1), dir(-1), dead(true) {}
	Fish(int _i, int _j, int _dir, bool _dead) :
		i(_i), j(_j), dir(_dir), dead(_dead) {
	}
};

vector<Fish> fishes;
vector<tuple<int, int, int>> eggs;
pair<int, int> shark;
vector<int> sharkPath;

long long maxEat;
vector<int> maxPath;

void Debug(int g[MAX_N][MAX_N]) {
	cout << endl;
	for (int i = 1; i < MAX_N; i++) {
		for (int j = 1; j < MAX_N; j++) {
			cout << g[i][j] << ' ';
		}
		cout << endl;
	}
	cout << endl;
}

void Init() {
	cin >> m >> s;
	for (int i = 1; i <= m; i++) {
		int ci, cj, cd;
		cin >> ci >> cj >> cd;
		fishes.push_back(Fish(ci, cj, cd, false));
		fishNumGrid[ci][cj]++;
	}

	cin >> shark.first >> shark.second;
}

void DupStart() {
	for (int f = 0; f < fishes.size(); f++) {
		eggs.push_back(make_tuple(fishes[f].i, fishes[f].j, fishes[f].dir));
	}
}

void DupFin() {
	for (int e = 0; e < eggs.size(); e++) {
		int ci, cj, cd;
		tie(ci, cj, cd) = eggs[e];
		fishes.push_back(Fish(ci, cj, cd, false));
		fishNumGrid[ci][cj]++;
	}

	eggs.clear();
}

bool InGrid(int i, int j) {
	return i >= 1 && i <= 4 && j >= 1 && j <= 4;
}

bool CanGo(int i, int j) {
	// 격자 밖
	if (!InGrid(i, j)) return false;
	// 상어가 있는 칸
	if (i == shark.first && j == shark.second) return false;
	// 물고기의 냄새가 있는 칸
	if (markGrid[i][j] != EMPTY) return false;

	return true;
}

void FishesMove() {
	for (int i = 0; i < fishes.size(); i++) {
		// 올 일이 없지만 혹시 몰라서 넣음
		if (fishes[i].dead) continue;

		int ci = fishes[i].i, cj = fishes[i].j, cd = fishes[i].dir;
		int ni = ci + ds[cd][0], nj = cj + ds[cd][1];
		int cnt = 0;
		while (!CanGo(ni, nj)) {
			cd = (cd - 1 == 0) ? 8 : cd - 1;
			ni = ci + ds[cd][0], nj = cj + ds[cd][1];
			cnt++;
			if (cnt == CANT_MOVE) break;
		}
		if (cnt == CANT_MOVE) continue;

		// 그리드 업데이트
		fishNumGrid[ci][cj]--, fishNumGrid[ni][nj]++;
		// 구조체 업데이트
		fishes[i].i = ni, fishes[i].j = nj, fishes[i].dir = cd;
	}
}

int Simulate() {
	long long curEat = 0;
	int ci = shark.first, cj = shark.second;
	int temp[MAX_N][MAX_N];
	for (int i = 1; i < MAX_N; i++) {
		for (int j = 1; j < MAX_N; j++) {
			temp[i][j] = fishNumGrid[i][j];
		}
	}

	for (int p = 0; p < 3; p++) {
		ci += sds[sharkPath[p]][0], cj += sds[sharkPath[p]][1];

		if (!InGrid(ci, cj)) return -1;
		curEat += temp[ci][cj];
		temp[ci][cj] = 0;
	}

	return curEat;
}

void GetPath() {
	if (sharkPath.size() == 3) {
		int curEat = Simulate();
		if (curEat > maxEat) {
			maxEat = curEat;
			maxPath = sharkPath;
		}
		return;
	}

	for (int d = 0; d < 4; d++) {
		sharkPath.push_back(d);
		GetPath();
		sharkPath.pop_back();
	}
}

void Eat() {
	int ci = shark.first, cj = shark.second;
	for (int i = 0; i < maxPath.size(); i++) {
		ci += sds[maxPath[i]][0], cj += sds[maxPath[i]][1];

		if (fishNumGrid[ci][cj] == EMPTY) continue;

		fishNumGrid[ci][cj] = 0;
		for (int f = 0; f < fishes.size(); f++) {
			if (fishes[f].i == ci && fishes[f].j == cj) {
				fishes[f].dead = true;
				markGrid[ci][cj] = turn;
			}
		}
	}

	shark.first = ci, shark.second = cj;
}

void SharkMove() {
	maxEat = -1;
	maxPath.clear();

	GetPath();

	Eat();
}

void EraseDeadFishes() {
	vector<Fish> temp;
	for (int i = 0; i < fishes.size(); i++) {
		if (fishes[i].dead) continue;
		temp.push_back(fishes[i]);
	}

	fishes = temp;
}

void EraseMark() {
	for (int i = 1; i < MAX_N; i++) {
		for (int j = 1; j < MAX_N; j++) {
			if (markGrid[i][j] == EMPTY) continue;
			if (markGrid[i][j] == turn - 2) markGrid[i][j] = EMPTY;
		}
	}
}

int main() {
	Init();

	while (++turn <= s) {
		DupStart();

		FishesMove();

		SharkMove();

		EraseDeadFishes();

		EraseMark();

		DupFin();
	}

	cout << fishes.size();

	return 0;
}

개선 후

#include <iostream>
#include <vector>

using namespace std;

#define MAX_N 5
#define DIR_NUM 9

int m, s;

// 물고기 방향: 1~8
// ←, ↖, ↑, ↗, →, ↘, ↓, ↙
const int fds[DIR_NUM][2] = {
    {0, 0},
    {0, -1},
    {-1, -1},
    {-1, 0},
    {-1, 1},
    {0, 1},
    {1, 1},
    {1, 0},
    {1, -1}
};

// 상어 방향: 상, 좌, 하, 우
const int sds[4][2] = {
    {-1, 0},
    {0, -1},
    {1, 0},
    {0, 1}
};

// board[i][j][d] = (i,j)에 방향 d인 물고기 수
int board[MAX_N][MAX_N][DIR_NUM];
int nxtBoard[MAX_N][MAX_N][DIR_NUM];
int copied[MAX_N][MAX_N][DIR_NUM];

// smell[i][j] = 냄새가 남겨진 턴 번호
int smell[MAX_N][MAX_N];

int sharkI, sharkJ;
int turn;

vector<int> path;
vector<int> bestPath;
int bestEat = -1;

bool InRange(int i, int j) {
    return (1 <= i && i <= 4 && 1 <= j && j <= 4);
}

void CopyStart() {
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            for (int d = 1; d <= 8; d++) {
                copied[i][j][d] = board[i][j][d];
            }
        }
    }
}

void MoveFish() {
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            for (int d = 1; d <= 8; d++) {
                nxtBoard[i][j][d] = 0;
            }
        }
    }

    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            for (int d = 1; d <= 8; d++) {
                int cnt = board[i][j][d];
                if (cnt == 0) continue;

                int nd = d;
                bool moved = false;

                for (int rot = 0; rot < 8; rot++) {
                    int ni = i + fds[nd][0];
                    int nj = j + fds[nd][1];

                    if (InRange(ni, nj) &&
                        !(ni == sharkI && nj == sharkJ) &&
                        smell[ni][nj] == 0) {
                        nxtBoard[ni][nj][nd] += cnt;
                        moved = true;
                        break;
                    }

                    nd--;
                    if (nd == 0) nd = 8;
                }

                if (!moved) {
                    nxtBoard[i][j][d] += cnt;
                }
            }
        }
    }

    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            for (int d = 1; d <= 8; d++) {
                board[i][j][d] = nxtBoard[i][j][d];
            }
        }
    }
}

int FishCountAt(int i, int j) {
    int sum = 0;
    for (int d = 1; d <= 8; d++) {
        sum += board[i][j][d];
    }
    return sum;
}

int SimulateShark() {
    int ci = sharkI;
    int cj = sharkJ;
    int eaten = 0;

    bool visited[MAX_N][MAX_N] = { false };

    for (int idx = 0; idx < 3; idx++) {
        int dir = path[idx];
        ci += sds[dir][0];
        cj += sds[dir][1];

        if (!InRange(ci, cj)) return -1;

        if (!visited[ci][cj]) {
            eaten += FishCountAt(ci, cj);
            visited[ci][cj] = true;
        }
    }

    return eaten;
}

void ChooseSharkPath() {
    if ((int)path.size() == 3) {
        int eaten = SimulateShark();
        if (eaten > bestEat) {
            bestEat = eaten;
            bestPath = path;
        }
        return;
    }

    for (int d = 0; d < 4; d++) {
        path.push_back(d);
        ChooseSharkPath();
        path.pop_back();
    }
}

void MoveShark() {
    bestEat = -1;
    bestPath.clear();
    path.clear();

    ChooseSharkPath();

    int ci = sharkI;
    int cj = sharkJ;

    for (int idx = 0; idx < 3; idx++) {
        int dir = bestPath[idx];
        ci += sds[dir][0];
        cj += sds[dir][1];

        int fishCnt = FishCountAt(ci, cj);
        if (fishCnt > 0) {
            for (int d = 1; d <= 8; d++) {
                board[ci][cj][d] = 0;
            }
            smell[ci][cj] = turn;
        }
    }

    sharkI = ci;
    sharkJ = cj;
}

void RemoveSmell() {
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            if (smell[i][j] != 0 && smell[i][j] <= turn - 2) {
                smell[i][j] = 0;
            }
        }
    }
}

void CopyFinish() {
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            for (int d = 1; d <= 8; d++) {
                board[i][j][d] += copied[i][j][d];
            }
        }
    }
}

int CountAllFish() {
    int total = 0;
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            for (int d = 1; d <= 8; d++) {
                total += board[i][j][d];
            }
        }
    }
    return total;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> m >> s;

    for (int k = 0; k < m; k++) {
        int i, j, d;
        cin >> i >> j >> d;
        board[i][j][d]++;
    }

    cin >> sharkI >> sharkJ;

    for (turn = 1; turn <= s; turn++) {
        CopyStart();
        MoveFish();
        MoveShark();
        RemoveSmell();
        CopyFinish();
    }

    cout << CountAllFish();

    return 0;
}