[백준 19236] 청소년 상어

[코드트리] 술래잡기 체스와 동일한 문제

https://www.codetree.ai/frequent-problems/odd-chess2/description

코드트리

메... 여전히 어려워 상어쉑....

https://www.acmicpc.net/problem/19236

19236번: 청소년 상어

#include <cstdio>
#include <cstring>

int board[4 + 2][4 + 2];	// 도둑말 번호만 표시해줌 

struct _pt
{
	int x, y;
	int d;
	bool alive = true;
};
_pt pin[16 + 2];

int sx, sy, sd;	// (술래말 위치, 방향)
int ans = 0;


void input()
{
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			int p = 0, d = 0;
			scanf("%d %d", &p, &d);
			board[i][j] = p;
			pin[p] = { i, j, d, true };
		}
	}

	// 초기에는 (0, 0)에 있는 도둑말을 잡으며 시작한다.
	sx = 0; sy = 0; sd = pin[board[0][0]].d;
	ans = board[0][0];

	pin[board[0][0]] = { -1, -1, -1, false };
	board[0][0] = 0;
}


void move_runner(int sx, int sy)
{
	// dir
	// 1↑, 2↖, 3←, 4↙, 5↓, 6↘, 7→, 8↗
	int dir_x[9] = { 0, -1, -1, 0, 1,  1, 1, 0, -1 };
	int dir_y[9] = { 0,  0, -1, -1, -1, 0, 1, 1, 1 };


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

		int x = pin[i].x;
		int y = pin[i].y;
		int d = pin[i].d;

		for (int p = 0; p < 8; p++) {
			int nd = (d + p);
			if (nd > 8) nd -= 8;
			int nx = x + dir_x[nd];
			int ny = y + dir_y[nd];

			if (nx < 0 || nx > 4 - 1 || ny < 0 || ny > 4 - 1) continue;
			if (nx == sx && ny == sy) continue;
			
			// 움직이려는 칸에 다른 도둑말이 있다면
			if (board[nx][ny] != 0) {
				int tmp = board[nx][ny];
				board[nx][ny] = i;
				pin[i] = { nx, ny, nd, true };
				board[x][y] = tmp;
				pin[tmp] = { x, y, pin[tmp].d, true };
				break;
			}
			else if (board[nx][ny] == 0){
				board[x][y] = 0;	// 원래 자기칸은 0으로 만들어줘야 분신술 안씀
				board[nx][ny] = i;
				pin[i] = { nx, ny, nd, true };
				break;
			}
		}
	}
}



void DFS(int x, int y, int p, int score)
{
	// dir
	// 1↑, 2↖, 3←, 4↙, 5↓, 6↘, 7→, 8↗
	static int dir_x[9] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };
	static int dir_y[9] = { 0,  0, -1, -1, -1, 0, 1, 1, 1 };

	// 도둑말 이동 
	move_runner(x, y);

	// 현재 상태 백업 
	int tmp_board[4 + 2][4 + 2];
	_pt tmp_pin[16 + 2];
	memset(tmp_board, 0, sizeof(board));
	memset(tmp_pin, 0, sizeof(pin));
	memcpy(tmp_board, board, sizeof(board));
	memcpy(tmp_pin, pin, sizeof(pin));


	// 술래말 이동 
	int end_game = 0;
	for (int s = 1; s <= 3; s++) {
		int nx = x + dir_x[p] * s;
		int ny = y + dir_y[p] * s;
		
		// 영역 벗어나거나 도둑말 없는 경우 
		if (nx < 0 || nx > 4 - 1 || ny < 0 || ny > 4 - 1 || board[nx][ny] == 0) {
			end_game++;
			continue;
		}
		// 도둑말 있어서 잡는 경우 
		if (board[nx][ny] != 0) {
			int pnum = board[nx][ny];
			int nd = pin[pnum].d;
			pin[pnum] = { -1, -1, -1, false };
			board[nx][ny] = 0;

			DFS(nx, ny, nd, score + pnum);
			
			// 조작하기 전의 상태로 원복
			memcpy(board, tmp_board, sizeof(board));
			memcpy(pin, tmp_pin, sizeof(pin));
		}
	}
	if (end_game == 3) {
		if (ans < score) ans = score;
		return;
	}
}


int main()
{
	input();
	DFS(sx, sy, sd, ans);	// (현재 술래 말 위치, 방향, 점수)
	printf("%d\n", ans);
	return 0;
}

++22.11.12  갱신

드디어 내 힘으로 청소년 상어를 풀었다. 자꾸 다른 테케 안나와서 진짜 기존 코드 보고싶었지만 꾹 참고 디버깅에 성공함... 

 

1. 술래말이 1칸 / 2칸 / 3칸 이동할 수 있기 때문에 모든 경우의 수를 탐색하기 위해 DFS를 사용해야 하는 문제이다. 

 

2. board정보 뿐 만 아니라, 현재 도둑말의 위치와 방향, 죽었는지 살았는지 여부를 저장해 놓은 구조체 pin도 같이 백업시켜 놓고, DFS 가 리턴할 때 원복시켜주어야 했다. 맵의 정보가 달라지는 것과 동일하게 도둑말의 정보도 함께 달라지기 때문이다. 

 

3. 리턴 조건을 어떻게 걸지 고민하다가, 술래말이 최대 3칸 까지 움직일 수 있는데 그 세번이 모두 영역 밖이거나 해당 칸에 도둑말이 없는 경우라면 ans를 갱신하고 리턴하도록 했다. 

이렇게 안하고 영역밖일때 ans 갱신 후 리턴해도 된다. 어차피 더 멀리 가봐야 영역밖이기 때문이다. 다만 이 방법으로 구현하는 경우, 해당 칸에 도둑말이 없는 경우는 continue로 스루해주어야 한다. 

 

4. 도둑말을 이동시킬 때 임시배열이 하나 더 필요할까 했는데, 굳이 사용하지 않아도 된다. 

그냥 교환시킬 도둑말 번호를 tmp 변수에 받아놓고 구조체 정보 갱신해주면된다. 

이때 중요한 것은 이동할 칸을 찾으면 break로 for 루프를 빠져나와야 한다는 것이다 ! 이거 안해주면 무한 분신사바가 됨...