[코드트리 모의시험] 삼성 공채 코딩테스트 모의3

1. 봄버맨 

https://www.codetree.ai/problems/bomber-man/description

코드트리

#include <cstdio>
#include <cstring>
#include <queue>
int N;
char board[7 + 2][7 + 2];
int bx, by;
int ans = -1;

struct _st
{
	int x, y;
};
std::queue<_st> Q;
std::queue<_st> TMP;


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



void input()
{
	scanf("%d", &N);
	for (int r = 0; r < N; r++) {
		scanf("%s", &board[r]);
		for (int c = 0; c < N; c++) {
			if (board[r][c] == 'B') {
				bx = r;
				by = c;
			}
		}
	}
}


bool chk_spread(int turn, int x, int y)
{
	Q = {};
	Q.push({ x, y });

	for (int loop = 1; loop <= turn; loop++) {
		TMP = {};
		while (!Q.empty()) {
			_st data = Q.front();
			Q.pop();

			for (int p = 0; p < 4; p++) {
				int nx = data.x + dir_x[p];
				int ny = data.y + dir_y[p];

				if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) return false;
				if (board[nx][ny] == '#') return false;
				TMP.push({ nx, ny });
			}
			TMP.push({ data.x, data.y });
		}
		Q = TMP;
	}
	return true;
}




void DFS(int turn, int x, int y)
{
	if (turn > ans) ans = turn;

	for (int p = 0; p < 4; p++) {
		int nx = x + dir_x[p];
		int ny = y + dir_y[p];

		if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
		if (board[nx][ny] == '#') continue;
		if (!chk_spread(turn + 1, nx, ny)) continue;
		//printf("%d %d %d\n", nx, ny, p);
		DFS(turn + 1, nx, ny);
	}
}




int main()
{
	input();
	DFS(0, bx, by);
	printf("%d\n", ans + 1);
	return 0;
}

자꾸 맵 복사 하려고 하지말고 조건문으로 처리할 수 있는 문제면 조건문으로 처리하기... 

정확한 원인은 모르겠지만 DFS + 맵복사로 돌렸었는데 그건 메모리 터진듯.. 

---

2. 테트리스 점수내기 

https://www.codetree.ai/problems/get-points-in-tetris/description

코드트리

#include <cstdio>
#include <cstring>
int R, C;
int board[50 + 2][50 + 2];
int tmp[50 + 2][50 + 2];
int ans;

int lookup[19 + 2][4][2] = {
	// 0
	{{0, 0}, {0, 1}, {0, 2}, {0, 3}},
	// 1
	{{0, 0}, {1, 0}, {2, 0}, {3, 0}},
	// 2
	{{0, 0}, {0, 1}, {1, 0}, {1, 1}},
	// 3
	{{0, 0}, {0, 1}, {0, 2}, {-1, 1}},
	// 4
	{{0, 0}, {1, 0}, {2, 0}, {1, 1}},
	// 5
	{{0, 0}, {0, 1}, {0, 2}, {1, 1}},
	// 6
	{{0, 0}, {1, 0}, {2, 0}, {1, -1}},
	// 7
	{{0, 0}, {1, 0}, {1, 1}, {1, 2}},
	// 8
	{{0 ,0}, {0, -1}, {1, -1}, {2, -1}},
	// 9
	{{0, 0}, {-1, 0}, {-1, -1}, {-1, -2}},
	// 10
	{{0, 0}, {0, 1}, {-1, 1}, {-2, 1}},
	// 11
	{{0, 0}, {-1, 0}, {-1, 1}, {-1, 2}},
	// 12
	{{0, 0}, {0, 1}, {1, 1}, {2, 1}},
	// 13
	{{0, 0}, {1, 0}, {1, -1}, {1, -2}},
	// 14
	{{0, 0}, {0, -1}, {-1 , -1}, {-2, -1}},
	// 15
	{{0, 0}, {0, 1}, {-1 ,1}, {-1 , 2}},
	// 16
	{{0, 0}, {1, 0}, {1, 1}, {2, 1}},
	// 17
	{{0, 0}, {0, 1}, {1, 1}, {1, 2}},
	// 18
	{{0, 0}, {1, 0}, {1, -1}, {2, -1}}
};


void input()
{
	scanf("%d %d", &R, &C);
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			scanf("%d", &board[r][c]);
		}
	}
}


bool can_set(int col, int block)
{
	// 백업
	memcpy(tmp, board, sizeof(tmp));

	int offset = -1;
	bool oob = false;
	bool get_end = false;
	bool meet_block = false;

	for (int r = 0; r < R; r++) {
		oob = false;
		for (int p = 0; p < 4; p++) {
			int x = r + lookup[block][p][0];
			int y = col + lookup[block][p][1];

			if (x < 0 || x > R - 1 || y < 0 || y > C - 1) {
				oob = true;
				break;
			}

			if (board[x][y] == 1) {
				meet_block = true;
				break;
			}
		
			if (x == R - 1) {
				get_end = true;
				break;
			}
		}
		if (meet_block) break;
		if (!oob) offset = r;
		if (get_end) break;
	}
	if (offset == -1) return false;

	// set 
	for (int p = 0; p < 4; p++) {
		int x = offset + lookup[block][p][0];
		int y = col + lookup[block][p][1];
		//printf("%d %d %d\n", x, y, oob);
		board[x][y] = 1;
	}
	return true;
}

int chk_score()
{
	int total = 0;
	int cnt = 0;

	for (int r = R - 1; r >= 0; r--) {
		cnt = 0;
		for (int c = 0; c < C; c++) {
			if (board[r][c] == 1) cnt++;
		}
		if (cnt == C) total++;
	}

	//debug();
	// undo
	memcpy(board, tmp, sizeof(tmp));
	return total;
}



void simulation()
{
	for (int c = 0; c < C; c++) {
		for (int b = 0; b < 19; b++) {
			if (!can_set(c, b)) continue;
			int res = chk_score();
			if (ans < res) ans = res;
		}
	}
}


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

테트로미노 + 모노미노도미노2 짬뽕문제.. 진짜 극혐 

로직은 간단하지만, 해당 블럭 자체가 영역을 벗어난 것인지 // 아래로 내려가면서 영역을 벗어나게 된 것인지 // 다른 블럭을 만나게 된 것인지에 대한 조건문을 잘 세워줘야 했다. 

1. 블럭들이 영역을 벗어나는지 아닌지에 대한 확인을 가장 먼저 해주어야 한다. 

2.블럭을 만나 이동을 중단해야 하는 상황인지에 대한 확인이 다음으로 온다. 

3. 가장 밑바닥에 닿았는지에 대한 확인이 가장 나중에 온다.