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

1. 하나가 되고싶어

ㅋ... 노답이네

https://www.codetree.ai/problems/want-to-be-one/description

코드트리

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
int N;
char board[5 + 2][5 + 2];
int ans = 0x7fffffff;

struct _st
{
	int x, y;
};
std::vector<_st> Wall;
std::vector<_st> Blank;
std::queue<_st> Q;
int visited[5 + 2][5 + 2];


void input()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%s", &board[i]);
		for (int j = 0; j < N; j++) {
			if (board[i][j] == '#') Wall.push_back({ i, j });
			else if (board[i][j] == '.') Blank.push_back({ i, j });
		}
	}
}


void BFS(int sx, int sy)
{
	//dir 
	int dir_x[4] = { 0, 0, 1, -1 };
	int dir_y[4] = { 1,-1, 0, 0 };

	// init
	Q = {};
	memset(visited, 0, sizeof(visited));
	Q.push({ sx, sy });
	visited[sx][sy] = 1;


	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) continue;
			if (board[nx][ny] == '#') continue;
			if (visited[nx][ny]) continue;
			Q.push({ nx, ny });
			visited[nx][ny] = 1;
		}
	}
}



int is_connected() // bfs	// 이어져있는지 
{
	BFS(Blank[0].x, Blank[0].y);

	//debug();

	// 빈칸 다 방문했는지 확인
	for (_st b : Blank) {
		if (visited[b.x][b.y] == 0) return false;
	}
	return true;
}


void DFS(int idx, int wall_cnt)
{
	if (wall_cnt > 6) return;
	if (ans < wall_cnt) return;
	if (idx == Wall.size()) {
		bool res = is_connected();
		if (res == true && ans > wall_cnt) ans = wall_cnt;
		return;
	}

	// 벽 부수지 않음 
	DFS(idx + 1, wall_cnt);

	// 벽 부숨
	board[Wall[idx].x][Wall[idx].y] = '.';
	DFS(idx + 1, wall_cnt + 1);
	board[Wall[idx].x][Wall[idx].y] = '#';
}



int main()
{
	input();
	if (Wall.size() == 0) printf("%d\n", 0);
	else {
		DFS(0, 0);	// 몇번째 벽 부술것인지	// 벽 몇개 부수었는지 
		if (ans == 0x7fffffff) printf("%d\n", -1);
		else printf("%d\n", ans);
	}
	return 0;
}

백준의 '벽 부수고 이동하기' 시리즈 인줄 알고 BFS로 방향 잡았다가 무려 1시간을 날려먹은 문제이다. 

DFS로 방향 잡고도 뭐에 씌였는지.. 계속 틀려서 고생 좀 했다. 

사실 간단하게 생각하면,

1. 특정 번째 벽을 부술 것인지 DFS로 조합의 경우의 수 구하기 

2. 경우의 수가 만들어지면 BFS 돌려서 각 영역이 이어져있는지 아닌지 탐색하기 

3. 만약 모든 빈칸을 방문했다면 true 리턴하여 ans 값 갱신하기

의 순서로 풀어주면 된다. 

 

풀이 보니까 2번, 3번 과정을 다음과 같이 Flood-Fill로 돌려서 그룹의 수를 세어주는 방식으로 풀었다. 

int group = 0;
for (int i = 0; i < N; i++) {
	for (int j = 0;j < N; j++) {
    	if (visited[i][j]) continue;
        BFS(i, j);
        group++;
    }
}

if (group != 1) return false;
return true;

왜 생각 못했을까.. 역시 문제 안푸니까 퇴화되기는 하는 듯.. 

---

2. 복잡한 핀볼게임

https://www.codetree.ai/problems/complex-pinball-game/description

코드트리

#include <cstdio>
#include <cstring>
#include <vector>
int N;
int board[10 + 2][10 + 2];
int choice[5 + 2];	// 입력으로 주어지는 3의 개수 최대 5개
int ans;
bool end_game;


struct _vt
{
	int x, y;
};
_vt Start_Points[40 + 2];
std::vector<_vt> Three;
std::vector<int> ball_loc[10 + 2][10 + 2];


int wall_lookup[3][4] = {
	// 0
	{},
	// 1 
	{1, 0, 3, 2},
	// 2
	{3, 2, 1, 0}
};


struct _st
{
	int x, y;
	int dir;
	bool alive;
	bool is_out;
};
_st Balls[40 + 2];	// 10 * 10 맵에 최대 4 * 10개 
_st Tmp_Balls[40 + 2];


void input()
{
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &board[i][j]);
			if (board[i][j] == 3) Three.push_back({ i, j });
		}
	}
	for (int i = 0; i < 4 * N; i++) {
		int b = 0;
		scanf("%d", &b);
		if (b == 1) Balls[i] = { -1, -1, -1, 1, 0 };
		else if (b == 0) Balls[i] = { -1, -1,-1, 0, 0 };
	}
}


void make_start_lookup()
{
	// dir
	// 우 하 좌 상
	int dir_x[4] = { 0, 1, 0, -1 };
	int dir_y[4] = { 1, 0, -1, 0 };

	// init
	int x = 1, y = 1, p = 0, num = 0;
	while (1) {
		if (num == 4 * N) break;
		Start_Points[num] = { x, y };
		num++;
		int nx = x + dir_x[p];
		int ny = y + dir_y[p];
		if (nx < 1 || nx > N || ny < 1 || ny > N ) {
			p = (p + 1) % 4;
			continue;
		}
		x = nx, y = ny;
	}

	// 각 공의 좌표 구하기 
	// 공이 경계에 있으므로 한칸씩 뒤로 미뤄주어야 한다. 
	int push_back[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
		
	for (int i = 0; i < 4 * N; i++) {
		if (Balls[i].alive == false) continue;
		int x = Start_Points[i].x + push_back[i / N][0];
		int y = Start_Points[i].y + push_back[i / N][1];
		Balls[i] = { x , y, i / N, 1, 0 };
	}
}



void move_ball()
{
	// dir
	// 하 좌 상 우
	int dir_x[4] = { 1, 0, -1, 0 };
	int dir_y[4] = { 0, -1, 0, 1 };


	for (int i = 0; i < 4 * N; i++) {
		if (Balls[i].alive == false) continue;
		int x = Balls[i].x;
		int y = Balls[i].y;
		int p = Balls[i].dir;
		
		int nx = x + dir_x[p];
		int ny = y + dir_y[p];

		if (nx < 1 || nx > N || ny < 1 || ny > N ) {
			Balls[i] = { nx, ny, p, false, true };
			continue;
		}
		int np = p;
		if (board[nx][ny] != 0) {
			np = wall_lookup[board[nx][ny]][p];
		}
		Balls[i].x = nx;
		Balls[i].y = ny;
		Balls[i].dir = np;
		ball_loc[nx][ny].push_back(i);
	}
}


void chk_crush()
{
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (ball_loc[i][j].size() >= 2) {
				for (int b : ball_loc[i][j]) {
					Balls[b].alive = false;
				}
			}
			ball_loc[i][j].clear();
		}
	}
}


int is_end()
{
	int is_out = 0;
	int is_dead = 0;

	for (int i = 0; i < 4 * N; i++) {
		if (Balls[i].alive == false) is_dead++;
		if (Balls[i].is_out == true) is_out++;
	}
	if (is_dead == 4 * N) end_game = true;
	return is_out;
}


int simulation()
{
	// 선택한 벽으로 바꾸기 
	for (int i = 0; i < Three.size(); i++) {
		board[Three[i].x][Three[i].y] = choice[i];
	}
	// 구슬 상태 백업 
	memcpy(Tmp_Balls, Balls, sizeof(Balls));
    
	// 시뮬진행
	end_game = false;
	int tmp = 0;
	while (1) {
		move_ball();
		chk_crush();
		int res = is_end();
		if (end_game == true) {
			tmp = res;
			break;
		}
	}

	// 원복
	for (int i = 0; i < Three.size(); i++) {
		board[Three[i].x][Three[i].y] = 3;
	}
	memcpy(Balls, Tmp_Balls, sizeof(Tmp_Balls));
	
	return tmp;
}


void DFS(int n)
{
	if (n == Three.size()) {
		//for (int i = 0; i < n; i++) printf("%d ", choice[i]);
		//printf("\n");
		int res = simulation();
		if (res > ans) ans = res;
		return;
	}


	for (int i = 0; i < 3; i++) {
		choice[n] = i;
		DFS(n + 1);
	}
}


int main()
{
	input();
	make_start_lookup();
	DFS(0);		// 몇번째 3을 선택하고 있는지 
	printf("%d\n", ans);
	return 0;
}

어으.. 가히 거zI같은 문제라고 할 수 있겠다. 

로직은 다음과 같다. 

 

1. 구슬 자리에 대한 룩업테이블을 만든다. 이때, 경계에서 시작하므로 구한 좌표에 대해서 한 칸씩 뒤로 미뤄주어야 한다. 

2. DFS를 돌려서 3 자리에 빈칸 / 1번 벽 / 2번 벽 중 어떤 것을 놓을지 선택한다. 

3. 조합의 수가 만들어지면 일단 처음 상태의 보드와 구슬 정보를 백업받아 놓고 시뮬레이션을 시작한다. 

이때 모든 구슬이 alive == false이면 루프를 멈춘다. 

simulation 함수의 리턴값은 영역 밖으로 나간 구슬의 수(is_out) 이다.

 

이것도 차근차근히 했으면 더 빨리 풀었을 텐데, 설계를 제대로 안하고 문제에 뛰어들어서 2시간 조금 넘게 걸렸다. 

의외로 1번이 엄청 오래걸렸다. 처음에는 경계에서 시작하는지 모르고 냅다 board안에 구슬을 위치시켰다가 테케 3번이 계속 안나와서 구슬 위치 찍어보니까 board 밖에서 시작이더라... 킁

그래서 일단 (1~N) 범위 안에서 달팽이 사각형 돌리면서 초기 구슬 위치 설정해주고, 상 / 하 / 좌 / 우 경계 위치에 따라 push_back이라는 룩업테이블 만들어서 하나씩 뒤로 미뤄주었다.