코드트리 술래잡기 (C++)

디버깅이 힘든 문제입니다. 그리고 술래가 바라보는 방향을 따로 저장해두는 것이 편했습니다.

도망자가 움직이는 move 함수, 술래가 잡은 도망자의 수를 리턴하는 check 함수, 술래가 바라보는 방향을 계산하는 indexing_m 함수와 m_reverse 함수로 구성했습니다.

술래는 달팽이 방향으로 움직이며 움직이는 방향으로 바라봅니다. 그러나 코너 위치에서 술래는 이동하자마자 방향을 바꿔버리기 때문에 이를 반영해야 합니다.

# 상 : 0
# 우 : 1
# 하 : 2
# 좌 : 3

# 정방향
2 1 1 1 2 
0 0 1 2 2 
0 0 0 2 2 
0 0 3 3 2 
0 3 3 3 3

# 역방향
2 2 3 3 3 
2 2 2 3 0 
2 2 0 0 0 
2 1 1 0 0 
1 1 1 1 0

 

	#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;
	typedef tuple<int,int,int> tiii;
	const int INF=1e9+1;
	int dx[4]={-1,0,1,0}, dy[4]={0,1,0,-1};
	vector<tiii> midx; // 술래의 움직일 방향을 인덱스로 접근
	void m_reverse(int n) {
	// 술래가 끝에 도달했을 때 바라보는 방향을 바꾸기 위한 함수
	// 처음과 마지막 위치에서의 바라보는 방향은 항상 고정된다
	for(auto& [x,y,d] : midx) d=d+2>3 ? (d+2)%4 : d+2;
	for(int i=n*n-1;i>0;i--) {
	auto& [x1,y1,d1]=midx[i];
	auto [x2,y2,d2]=midx[i-1];
	if(d1!=d2) d1=d2;
	}
	auto& [x1,y1,d1]=midx[0];
	d1=0;
	auto& [x2,y2,d2]=midx[n*n-1];
	d2=2;
	}
	int check(vector<vector<int>>& tree, vector<pair<pii,pii>>& B, int aidx) {
	// 술래가 바라보는 방향에서 잡은 도망자의 수를 리턴하는 함수
	// 한 곳에 여러명의 도망자가 위치할 수 있다
	int n=tree.size();
	vector<vector<int>> board(n,vector<int>(n));
	for(auto [spot,info] : B) board[spot.first][spot.second]++;
	auto [sx,sy,dir]=midx[aidx];
	int ret=0;
	for(int i=0;i<=2;i++) {
	int nx=sx+dx[dir]*i, ny=sy+dy[dir]*i;
	if(nx>=0 && nx<n && ny>=0 && ny<n) {
	if(board[nx][ny] && !tree[nx][ny]) {
	ret+=board[nx][ny];
	board[nx][ny]=0;
	}
	}
	}
	// 잡힌 도망자를 도망자 리스트에서 제거
	vector<pair<pii,pii>> B_prime;
	for(auto [spot,info] : B) {
	if(board[spot.first][spot.second]) B_prime.push_back({spot,info});
	}
	B=B_prime;
	return ret;
	}
	vector<pair<pii,pii>> move(int n, vector<pair<pii,pii>>& B, int aidx) {
	// 도망자가 움직이기 위한 함수
	int t1_dx[2]={0,0}, t1_dy[2]={1,-1};
	int t2_dx[2]={1,-1}, t2_dy[2]={0,0};
	vector<pair<pii,pii>> r;
	auto [sx,sy,d]=midx[aidx];
	for(auto [spot, info] : B) {
	auto [x,y]=spot;
	auto [t,d]=info;
	if(abs(x-sx)+abs(y-sy)>3) {
	r.push_back({spot,info});
	continue;
	};
	int nx,ny;
	if(t==1) nx=x+t1_dx[d], ny=y+t1_dy[d];
	else nx=x+t2_dx[d], ny=y+t2_dy[d];
	// 가고자 하는 위치에 술래가 있으면 정지
	if(nx==sx && ny==sy) {
	r.push_back({{x,y},{t,d}});
	continue;
	}
	// 범위를 초과한다면 반대 방향으로 이동하려고 한다
	if(!(nx>=0 && nx<n && ny>=0 && ny<n)) {
	d=(d+1)%2;
	if(t==1) nx=x+t1_dx[d], ny=y+t1_dy[d];
	else nx=x+t2_dx[d], ny=y+t2_dy[d];
	// 가고자 하는 위치에 술래가 있으면 정지
	if(nx==sx && ny==sy) {
	r.push_back({{x,y},{t,d}});
	continue;
	}
	}
	r.push_back({{nx,ny},{t,d}});
	}
	return r;
	}
	void indexing_A(int n) {
	// 달팽이 모양으로 움직이기 위한 인덱싱
	// dx,dy는 달팽이 방향과 같이 상,오,하,왼 순으로 저장해둔다
	int ax=n/2, ay=n/2;
	midx.push_back({ax,ay,0});
	int dist=1, dir=0;
	bool flag=true;
	while(flag) {
	int cnt=2;
	while(flag && cnt--) {
	for(int i=0;i<dist;i++) {
	if(!flag) break;
	ax+=dx[dir];
	ay+=dy[dir];
	if(i==dist-1) {
	int tdir=dir+1==4 ? 0 : dir+1;
	midx.push_back({ax,ay,tdir});
	}
	else midx.push_back({ax,ay,dir});
	if(ax==0 && ay==0) flag=false;
	}
	dir=dir+1==4 ? 0 : dir+1;
	}
	dist++;
	}
	// (0,0)에서 바라보는 방향은 항상 아래쪽이다
	auto& [a,b,c]=midx[n*n-1];
	c=2;
	}
	int main() {
	fastio
	int n,m,h,k; cin>>n>>m>>h>>k;
	vector<vector<int>> tree(n,vector<int>(n));
	vector<pair<pii,pii>> B;
	while(m--) {
	int x,y,t; cin>>x>>y>>t;
	B.push_back({{x-1,y-1},{t,0}});
	}
	while(h--) {
	int x,y; cin>>x>>y;
	tree[x-1][y-1]=1;
	}
	indexing_A(n);
	int aidx=0, ans=0, p=1;
	for(int t=1;t<=k;t++) {
	B=move(n,B,aidx);
	// 술래는 항상 달팽이 모양으로 움직인다
	// 만약 끝에 다다르면 바라보는 방향을 바꿔야 한다
	aidx+=p;
	if(p>0 && aidx==n*n-1) p*=-1, m_reverse(n);
	else if(p<0 && aidx==0) p*=-1, m_reverse(n);
	ans+=t*check(tree,B,aidx);
	}
	cout<<ans<<endl;
	return 0;
	}

view raw codetree_seecker_and_hider.cpp hosted with ❤ by GitHub