[코드트리 44] 술래잡기

++ 22.12.12 갱신

 

https://www.codetree.ai/training-field/frequent-problems/hide-and-seek/description?page=3&pageSize=20 

코드트리

 

#include <cstdio>
#include <cstring>
#include <cmath>
int N, M, H, K;

struct _st
{
	int x, y;
	int dir;
	bool alive;
};
_st Runner[10000 + 2];

int Tree[100 + 2][100 + 2];


struct _ct
{
	int x, y;
};
_ct Catcher_NPOS[10000 + 2];	// 달팽이 정방
int Catcher_NDIR[10000 + 2];
_ct Catcher_CPOS[10000 + 2];	// 달팽이 역방
int Catcher_CDIR[10000 + 2];	
int c_flag;	// 0이면 정방향 1이면 역방향
int c_num = 1;
int cx, cy;
int cdir;

int catcher[100 + 2][100 + 2];	// 디버깅용



void input()
{
	scanf("%d %d %d %d", &N, &M, &H, &K);
	for (int i = 1; i <= M; i++) {
		int x = 0, y = 0, dir = 0;
		scanf("%d %d %d", &x, &y, &dir);
		Runner[i] = { x, y, dir, true };
	}
	for (int i = 1; i <= H; i++) {
		int x = 0, y = 0;
		scanf("%d %d", &x, &y);
		Tree[x][y] = 1;
	}
}


void make_catcher_route_ndir()
{
	// 달팽이 정방 
	int dir_x[4] = { -1, 0, 1, 0 };
	int dir_y[4] = { 0, 1, 0, -1 };

	int x = (N + 1) / 2;
	int y = (N + 1) / 2;
	int  p = 0;
	int num = 1; //for debug

	Catcher_NPOS[num] = { x, y };
	Catcher_NDIR[num - 1] = p;
	catcher[x][y] = num;

	for (int n = 1; n <= N - 1; n++) {
		for (int i = 0; i < 3; i++) {
			if (i == 2 && n != N - 1) break;
			for (int step = 1; step <= n; step++) {
				int nx = x + dir_x[p];
				int ny = y + dir_y[p];
				num++;
				x = nx, y = ny;
				Catcher_NPOS[num] = { nx, ny };
				Catcher_NDIR[num - 1] = p;
				//printf("%d %d %d\n", num, nx, ny);
				catcher[nx][ny] = num;
			}
			p = (p + 1) % 4;
		}
	}
	//debug(0);
}


void make_catcher_route_cdir()
{
	// init
	memset(catcher, 0, sizeof(catcher));

	// 달팽이 역방 
	int dir_x[4] = { -1, 0, 1, 0 };
	int dir_y[4] = { 0, 1, 0, -1 };
	int trans[4] = { 2, 1, 0, 3 };

	int x = 1;
	int y = 1;
	int p = 0;
	int num = N * N;	// for debug

	Catcher_CPOS[num] = { x, y };
	Catcher_CDIR[num + 1] = trans[p];
	catcher[x][y] = num;

	while (1) {
		if (num == 1) break;		
		int nx = x + dir_x[trans[p]];
		int ny = y + dir_y[trans[p]];
		if (nx < 1 || nx > N || ny < 1 || ny > N || catcher[nx][ny]) {
			p = (p + 1) % 4;
			continue;
		}
		num--;
		Catcher_CPOS[num] = { nx, ny };
		Catcher_CDIR[num + 1] = trans[p];
		catcher[nx][ny] = num;
		x = nx, y = ny;
	}
	//debug(0);
}


void move_runners()
{
	// dir
	int dir_x[4] = { 0, 0, 1, -1 };
	int dir_y[4] = { -1, 1, 0, 0 };
	int dir_op[4] = { 1, 0, 3, 2 };


	for (int i = 1; i <= M; i++) {
		if (Runner[i].alive == false) continue;
		if (abs(cx - Runner[i].x) + abs(cy - Runner[i].y) > 3) continue;

		int x = Runner[i].x;
		int y = Runner[i].y;
		int p = Runner[i].dir;
		int np = p;

		int nx = x + dir_x[p];
		int ny = y + dir_y[p];

		// 현재 바라보고 있는 방향으로 한 칸 움직일 때 격자를 벗어나는 경우 
		if (nx < 1 || nx > N || ny < 1 || ny > N) {
			np = dir_op[p];
			nx = x + dir_x[np];
			ny = y + dir_y[np];
			if (nx == cx && ny == cy) continue;
			Runner[i] = { nx, ny, np, true };
			continue;
		}
		// 격자를 벗어나지 않는 경우 
		else {
			if (nx == cx && ny == cy) continue;	// 술래가 있다면 움직이지 않는다. 
			Runner[i] = { nx, ny, p, true };
			continue;
		}
	}
	//debug(1);
}



int move_catcher()
{
	// dir 
	int dir_x[4] = { -1, 0, 1, 0 };
	int dir_y[4] = { 0, 1, 0, -1 };


	if (c_flag == 0) c_num++;
	else if (c_flag == 1) c_num--;

	if (c_flag == 0 && c_num == N * N) c_flag = 1;
	if (c_flag == 1 && c_num == 1) c_flag = 0;

	if (c_flag == 0) {
		cx = Catcher_NPOS[c_num].x;
		cy = Catcher_NPOS[c_num].y;
		cdir = Catcher_NDIR[c_num];
	}
	else if (c_flag == 1) {
		cx = Catcher_CPOS[c_num].x;
		cy = Catcher_CPOS[c_num].y;
		cdir = Catcher_CDIR[c_num];
	}

	//printf("[%d] (%d %d) >>%d %d\n", c_num, cx, cy, cdir, c_flag);

	int catch_runner = 0;
	for (int i = 0; i <= 2; i++) {
		int nx = cx + dir_x[cdir] * i;
		int ny = cy + dir_y[cdir] * i;
		if (Tree[nx][ny]) continue;
		for (int i = 1; i <= M; i++) {
			if (Runner[i].alive == false) continue;
			if (nx == Runner[i].x && ny == Runner[i].y) {
				Runner[i].alive = false;
				catch_runner++;
			}
		}
	}
	return catch_runner;
}




int simulation()
{
	int score = 0;
	cx = cy = (N + 1) / 2;

	for (int t = 1; t <= K; t++) {
		move_runners();
		int res = move_catcher();
		score += (t * res);
	}
	return score;
}





int main()
{
	input();
	make_catcher_route_ndir();
	make_catcher_route_cdir();
	int ans = simulation();
	printf("%d\n", ans);
	return 0;
}

내가 했던 치명적인 실수 3개 

1. 인덱스 실수

최대 99 * 99 사이즈가 될 수 있고, 도망자도 최대 N^2까지 존재할 수 있으므로 구조체 배열 사이즈를 100 + 2 이 아닌 10000 + 2로 줬어야 한다. 

2. 뭐가 문제인지 알고 나서 제출시스템에서만 고치고 로컬 코드를 안고침. 그러니까 수정하고 다시 냈을 때 또 틀림

무조건 로컬에서 고치고 -> 복붙해서 채점 시스템 돌려보자

3. 로직 실수

한번 죽은 도망자는 다시 잡으면 안된다. 따라서 if (alive == false)이면 넘겨주어야 한다 .

---

기부니가 째지거든요~

#include <cstdio>
#include <vector>
#include <cstdlib>
int N, M, H, K;

struct _ct
{
	int num;
	int dir;
};

struct _lt
{
	int x, y;
	int dir;
};

_ct C_Route[99 + 2][99 + 2];		// 술래이동 경로    //디버깅용
_lt lookup[10000 + 2];
_ct C_Route_rev[99 + 2][99 + 2];	// 술래이동 역경로	// 디버깅용
_lt lookup_rev[10000 + 2];

int cx, cy, cnum, cdir, cflag;	// 술래 위치 좌표, 현재 어떤 숫자에 있는지, 어느 방향 보고있는지 
								// 어떤 방향 보고 가고 있는지 정방향0, 역방향1 

int Tree[99 + 2][99 + 2];

struct _rt
{
	int r, c;
	int d;
	bool alive;
};

_rt Runner[10000 + 2];
std::vector<int> Run[99 + 2][99 + 2];
std::vector<int> Tmp[99 + 2][99 + 2];




void input()
{
	scanf("%d %d %d %d", &N, &M, &H, &K);
	for (int i = 1; i <= M; i++) {
		int x = 0, y = 0, d = 0;
		scanf("%d %d %d", &x, &y, &d);
		Runner[i] = { x, y, d, true };	// d = 1 좌우로 움직임 우측부터 시작
										// d = 2 상하로 움직임 아래부터 시작
		Run[x][y].push_back(i);			// 해당 격자에 몇번째 도망자가 있는지 표시
	}
	for (int i = 1; i <= H; i++) {
		int r = 0, c = 0;
		scanf("%d %d", &r, &c);
		Tree[r][c] = 1;
	}
}


void make_catcher_route()
{
	// 하 우 상 좌
	static int dir_x[4] = { 1, 0, -1, 0 };
	static int dir_y[4] = { 0, 1, 0, -1 };
	// 정방향 순서 : 상 우 하 좌
	static int ch[4] = { 2, 1, 0, 3 };

	// 정방향 
	int gx = (N + 1) / 2, gy = (N + 1) / 2, gdir = 0;
	int gnum = 1;

	for (int i = 1; i <= N; i++) {
		for (int d = 0; d < 2; d++) {
			for (int j = 1; j <= i; j++) {
				C_Route[gx][gy] = { gnum, ch[gdir] };
				lookup[gnum] = { gx, gy, ch[gdir] };

				gx += dir_x[ch[gdir]];
				gy += dir_y[ch[gdir]];
				gnum++;
			}
			gdir = (gdir + 1) % 4;
		}
	}

	// 역방향 
	int rx = 1, ry = 1, rdir = 0;
	int rnum = N * N;

	for (int i = 1; i <= N * N + N + N; i++) {
		C_Route_rev[rx][ry] = { rnum, rdir };
		lookup_rev[rnum] = { rx, ry, rdir };

		int nx = rx + dir_x[rdir];
		int ny = ry + dir_y[rdir];
		if (nx < 1 || nx > N || ny < 1 || ny > N || C_Route_rev[nx][ny].num != 0) {
			rdir = (rdir + 1) % 4;
			continue;
		}
		rx = nx, ry = ny;
		rnum--;
	}

	// 처음 술래는 항상 정중앙 위치
	cx = cy = (N + 1) / 2;
	cnum = 1;
}



void move_runner()
{
	// 0좌 1우 2하 3상
	static int dir_x[4] = { 0, 0, 1, -1 };
	static int dir_y[4] = { -1, 1, 0, 0 };
	static int ch[4] = { 1, 0, 3, 2 };

	// Tmp init
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			Tmp[i][j].clear();
		}
	}


	for (int i = 1; i <= M; i++) {
		if (Runner[i].alive == false) continue;

		int x = Runner[i].r;
		int y = Runner[i].c;
		int d = Runner[i].d;

		if (abs(x - cx) + abs(y - cy) > 3) {
			Tmp[x][y].push_back(i);
			continue;
		}

		int nx = x + dir_x[d];
		int ny = y + dir_y[d];
		if (nx < 1 || nx > N || ny < 1 || ny > N) {
			d = ch[d];
			nx = x + dir_x[d];
			ny = y + dir_y[d];
			if (nx == cx && ny == cy) {
				Runner[i] = { x, y, d, true };	// 방향만 갱신 
				Tmp[x][y].push_back(i);
			}
			else {
				Runner[i] = { nx, ny, d, true };
				Tmp[nx][ny].push_back(i);
			}
			continue;
		}
		if (nx == cx && ny == cy) {
			Tmp[x][y].push_back(i);
			continue;
		}
		Runner[i] = { nx, ny, d , true };
		Tmp[nx][ny].push_back(i);
	}

	// Run init
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			Run[i][j].clear();
		}
	}

	// Cpy
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			Run[i][j] = Tmp[i][j];
		}
	}
}




void move_catcher()
{
	if (cflag == 0) cnum++;
	else cnum--;
	if (cflag == 0) {
		cx = lookup[cnum].x;
		cy = lookup[cnum].y;
		cdir = lookup[cnum].dir;
	}
	else {
		cx = lookup_rev[cnum].x;
		cy = lookup_rev[cnum].y;
		cdir = lookup_rev[cnum].dir;
	}
	if (cnum == N * N) cflag = 1;
	if (cnum == 1) cflag = 0;
}



int catch_runner()
{
	// 하 우 상 좌
	static int dir_x[4] = { 1, 0, -1, 0 };
	static int dir_y[4] = { 0, 1, 0, -1 };
	int cnt = 0;


	for (int s = 0; s < 3; s++) {
		int nx = cx + dir_x[cdir] * s;
		int ny = cy + dir_y[cdir] * s;

		if (nx < 1 || nx > N || ny < 1 || ny > N) continue;
		if (Tree[nx][ny]) continue;
		if (!Run[nx][ny].empty()) {
			for (int r : Run[nx][ny]) {
				Runner[r] = { -1, -1, -1, false };
			}
			cnt += Run[nx][ny].size();
			Run[nx][ny].clear();
		}
	}
	return cnt;
}



int simulation()
{
	int score = 0;
	for (int k = 1; k <= K; k++) {
		move_runner();
		move_catcher();
		score += (catch_runner() * k);
	}
	return score;
}


int main()
{
	input();
	make_catcher_route();
	int ans = simulation();
	printf("%d\n", ans);
	return 0;
}

아무래도 중요했던건 술래 이동 로직이 아니었나 싶다. 빙글빙글 달팽이 사각형...

나는 정방향 역방향 따로따로 룩업테이블 만들어서 해당 숫자의 위치에서 술래가 어떤 방향을 바라보고 있어야 하는지 저장했다.