백준 23290 마법사 상어와 복제(C++)

상어의 마법 연습 한 번은 다음과 같은 작업이 순차적으로 이루어진다.
  1. 상어가 모든 물고기에게 복제 마법을 시전한다. 복제 마법은 시간이 조금 걸리기 때문에, 아래 5번에서 물고기가 복제되어 칸에 나타난다.
  2. 모든 물고기가 한 칸 이동한다. 상어가 있는 칸, 물고기의 냄새가 있는 칸, 격자의 범위를 벗어나는 칸으로는 이동할 수 없다. 각 물고기는 자신이 가지고 있는 이동 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기의 냄새는 아래 3에서 설명한다.
  3. 상어가 연속해서 3칸 이동한다. 상어는 현재 칸에서 상하좌우로 인접한 칸으로 이동할 수 있다. 연속해서 이동하는 칸 중에 격자의 범위를 벗어나는 칸이 있으면, 그 방법은 불가능한 이동 방법이다. 연속해서 이동하는 중에 상어가 물고기가 있는 같은 칸으로 이동하게 된다면, 그 칸에 있는 모든 물고기는 격자에서 제외되며, 제외되는 모든 물고기는 물고기 냄새를 남긴다. 가능한 이동 방법 중에서 제외되는 물고기의 수가 가장 많은 방법으로 이동하며, 그러한 방법이 여러가지인 경우 사전 순으로 가장 앞서는 방법을 이용한다. 사전 순에 대한 문제의 하단 노트에 있다.
  4. 두 번 전 연습에서 생긴 물고기의 냄새가 격자에서 사라진다.
  5. 1에서 사용한 복제 마법이 완료된다. 모든 복제된 물고기는 1에서의 위치와 방향을 그대로 갖게 된다.

이 문제 역시 위의 설명을 따라가면서 구현하면 됩니다. 물고기를 이동시키는 함수, 상어를 이동시키는 함수, 냄새를 관리하는 함수로 나눠 생각할 수 있습니다. 그리고 하나의 칸에 여러 마리의 물고기가 동시에 있을 수 있으므로 2차원 deque 배열을 사용했습니다. 구현하면서 냄새 관리만 주의하면 될 것 같습니다.

	#include <bits/stdc++.h>
	#define endl '\n'
	#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	using namespace std;
	typedef long long ll;
	typedef pair<int,int> pii;
	typedef pair<ll, ll> pll;
	const int INF=1e9+1;
	int dx[]={0,0,-1,-1,-1,0,1,1,1};
	int dy[]={0,-1,-1,0,1,1,1,0,-1};
	bool movable(int x, int y, deque<vector<int>>& smell) {
	// 냄세가 남아있는 칸에 접근하지 못하도록 하는 함수
	for(auto v : smell) {
	if(v[0]==x && v[1]==y) return 0;
	}
	return 1;
	}
	void smell_remove(deque<vector<int>>& smell) {
	// 냄세 제거
	for(auto& v : smell) {
	v[2]--;
	if(!v[2]) smell.pop_front();
	}
	}
	vector<vector<deque<int>>> fish_move(int sx, int sy, vector<vector<deque<int>>>& board, deque<vector<int>>& smell) {
	// 물고기 이동
	vector<vector<deque<int>>> ret(5,vector<deque<int>>(5));
	for(int i=1;i<=4;i++) {
	for(int j=1;j<=4;j++) {
	deque<int> dq = board[i][j];
	while(!dq.empty()) {
	int dir=dq.front(); dq.pop_front();
	int t=8;
	bool ismove=false;
	while(t--) {
	int nx=i+dx[dir], ny=j+dy[dir];
	if(nx>0 && nx<5 && ny>0 && ny<5 && movable(nx,ny,smell) && !(nx==sx && ny==sy)) {
	ret[nx][ny].push_back(dir);
	ismove=true;
	break;
	}
	dir--;
	if(dir==0) dir=8;
	}
	if(!ismove) ret[i][j].push_back(dir);
	}
	}
	}
	return ret;
	}
	void shark_move(int& sx, int& sy, vector<vector<deque<int>>>& board, deque<vector<int>>& smell) {
	// 상어 이동
	int sdir[5]={0,3,1,7,5};
	vector<vector<int>> v; // (1,1,1)부터 (4,4,4)까지 저장
	for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) for(int k=1;k<=4;k++) v.push_back({i,j,k});
	vector<pair<int,string>> v2;
	// 각 이동방향에 따라 먹을 수 있을 물고기 수를 세어 v2에 저장
	for(auto it : v) {
	string s=to_string(it[0])+to_string(it[1])+to_string(it[2]);
	vector<vector<int>> visit(5,vector<int>(5));
	int nsx=sx, nsy=sy;
	int fishes=0;
	bool flag=true;
	for(auto d : it) {
	nsx+=dx[sdir[d]], nsy+=dy[sdir[d]];
	if(nsx>0 && nsx<=4 && nsy>0 && nsy<=4) {
	if(!visit[nsx][nsy]) fishes+=board[nsx][nsy].size(), visit[nsx][nsy]=1;
	}
	else {
	flag=false;
	break;
	}
	}
	if(flag) v2.push_back({-fishes,s});
	}
	sort(v2.begin(),v2.end());
	// 가장 많은 물고기를 먹을 수 있는 이동방향으로 상어 이동, 물고기 냄세 기록
	auto [cnt, direction] = v2.front();
	for(char c : direction) {
	int d=sdir[c-'0'];
	sx+=dx[d], sy+=dy[d];
	if(board[sx][sy].size()) {
	smell.push_back({sx,sy,3});
	while(!board[sx][sy].empty()) board[sx][sy].pop_front();
	}
	}
	}
	int main() {
	fastio
	//freopen("input.txt","r",stdin);
	int m,s; cin>>m>>s;
	vector<vector<deque<int>>> board(5,vector<deque<int>>(5));
	deque<vector<int>> smell;
	while(m--) {
	int x,y,d; cin>>x>>y>>d;
	board[x][y].push_back(d);
	}
	int sx,sy; cin>>sx>>sy;
	while(s--) {
	// copy
	vector<vector<int>> temp;
	for(int i=1;i<=4;i++) {
	for(int j=1;j<=4;j++) {
	if(!board[i][j].empty()) {
	for(auto it : board[i][j]) temp.push_back({i,j,it});
	}
	}
	}
	// fish move
	board=fish_move(sx,sy,board,smell);
	// shark move
	shark_move(sx,sy,board,smell);
	// smell update
	smell_remove(smell);
	// copy
	for(auto v : temp) board[v[0]][v[1]].push_back(v[2]);
	}
	int ans=0;
	for(int i=1;i<=4;i++) {
	for(int j=1;j<=4;j++) {
	if(board[i][j].empty()) continue;
	ans+=board[i][j].size();
	}
	}
	cout<<ans;
	return 0;
	}

view raw boj23290.cpp hosted with ❤ by GitHub