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

공교롭게도 둘 다 첫시도에서 AC를 받았는데.. 시험때도 이렇게만 풀고 나와라 ~~~ 나자신 ~~

1. 동전 챙기기

https://www.codetree.ai/problems/collect-coins/description

코드트리

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
int N;
char board[20 + 2][20 + 2];
int sx, sy;
int ex, ey;

int cur_x;
int cur_y;

struct _st
{
	int x, y;
	int coin;
};

bool compare(const _st &a, const _st &b)
{
	return a.coin < b.coin;
}
std::vector<_st> V;
int v_cnt;
int choice[9 + 2];
int ans = 0x7fffffff;

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

int visited[20 + 2][20 + 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] >= '1' && board[i][j] <= '9') {
				V.push_back({ i, j, board[i][j] - '0' });
			}
			else if (board[i][j] == 'S') {
				sx = i;
				sy = j;
				board[i][j] = '.';
			}
			else if (board[i][j] == 'E') {
				ex = i;
				ey = j;
				board[i][j] = '.';
			}
		}
	}
	std::sort(V.begin(), V.end(), compare);
	v_cnt = V.size();
	//printf("%d %d\n", V.front().coin, V.back().coin);
}


int BFS(int next_x, int next_y)	// 중간중간 도착지
{
	// init
	Q = {};
	memset(visited, 0, sizeof(visited));

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

	Q.push({ cur_x, cur_y });
	visited[cur_x][cur_y] = 1;

	while (!Q.empty()) {
		_qt data = Q.front();
		Q.pop();

		if (data.x == next_x && data.y == next_y) return visited[data.x][data.y] - 1;

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


int Flood_Fill()
{
	int total = 0;
	int res = 0;
	cur_x = sx;	// 항상 출발점에서 시작
	cur_y = sy;	
	for (int i = 0; i < 3; i++) {
		res = BFS(V[choice[i]].x, V[choice[i]].y);
		if (res == -1) return -1;
		total += res;
		cur_x = V[choice[i]].x;		// 다음 출발지
		cur_y = V[choice[i]].y;	
	}
	res = BFS(ex, ey);	// 목적지까지 한번 더 가야됨 
	if (res == -1) return -1;
	total += res;
	return total;
}




void DFS(int n, int s)
{
	if (n >= 3) {
		int dist = Flood_Fill();
		if (dist == -1) return;
		if (ans > dist) ans = dist;
		return;
	}

	if (n == v_cnt) return;
	
	for (int i = s; i < v_cnt; i++) {
		choice[n] = i;
		DFS(n + 1, i + 1);
	}
}



int main()
{
	input();
	DFS(0, 0);
	if (ans == 0x7fffffff) printf("%d\n", -1);
	else printf("%d\n", ans);
	return 0;
}

신기한 Bucket 먼저 풀고 쳐맞아서 그런가 비교적 스근히 풀린 동전 챙기기..

그러고 보니 둘 다 DFS가 가미된 문제다.. 

 

1. "최소 3개의 동전"을 주워야 한다고 해서 처음에는 3개 이상일 때도 모두 탐색해보아야 하나 싶었다. 그런데 "해당 위치를 지나가더라도 동전을 수집하지 않아도 되며"라는 문제 설명을 보고 DFS 탐색 종료조건을 n >= 3 일 때로 설정했다. 오히려 동전을 더 많이 주울수록 이동경로가 커질 수 있기 때문이다. 

 

2. "동전에 적혀있는 숫자가 증가하는 순서대로 수집"해야되기 때문에, 일단 맵을 input 받으면서 동전의 위치와 동전의 숫자를 벡터에 저장하고, compare 함수를 만들어서 오름차순으로 sort 해주었다. 

이렇게 해 놓으면 조합으로 경우의 수를 구할 때, 무조건 오름차순으로 선택하게 된다. 

(예컨대 벡터의 0, 1, 2번째 동전을 고른다고 하면 무조건 1 -> 2 -> 3번 순서로 choice 배열에 담긴다. 따라서 BFS 탐색 시에 따로 조작해줄 필요가 전혀 없음)

 

3. 동전을 줍는 과정은 BFS로 구현했다. 

이때 "같은 위치를  2번 이상 지나가는 것 역시 허용된다"고 해서 처음에는 비트마스킹해야하나.. ? 싶었다. 그런데 어차피 최대 20 * 20 맵이고, 동전이 최대 9개 들어오는데 그 중 3개를 선택하는 조합의 경우의 수를 다 곱해도 연산량이 40,000번 이하이기 때문에 그냥 각 경우의 수 마다 BFS 4번 돌려주었다. 

시작점 -> 처음 동전위치 -> 두번째 동전 위치 -> 세번째 동전위치 -> 끝점 

이런식으로 BFS 4번 돌려서 각각의 거리를 가져오고, 만약 벽에 가로막혀서 이동하지 못하는 경우 -1을 리턴하여 바로 BFS 탐색을 끝내고 DFS 함수로 돌아오게끔 하였다. 

---

2. 신기한 Bucket

https://www.codetree.ai/problems/special-bucket/description

코드트리

//1h 50m
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
int N;	// 블럭 최대 100개까지 들어올 수 있음
int board[200 + 2][4 + 2];	// 200까지 안줘도 된다.	// 블럭은 N개밖에 없으므로 한 열에 최대 100개까지 쌓여도 최대 높이 100 + 1개임
int d_tmp[200 + 2][4 + 2];
int tmp[200 + 2][4 + 2];
int ans;

// 0 1↑, 2↖, 3←, 4↙, 5↓, 6↘, 7→, 8↗ 
int lookup[9][9];	// 각 블럭의 이동 우선순위

struct _st
{
	int k, c;
};
_st CMD[100 + 2];
int choice[4 + 2];	// c가 0으로 주어지는 횟수는 최대 4
int c_cnt;


struct _vt
{
	int x, y;
};
std::vector<_vt> V;


void input()
{
	scanf("%d", &N);
	for (int i = 1; i <= 8; i++) {
		for (int d = 1; d <= 8; d++) {
			scanf("%d", &lookup[i][d]);	// i번째 블럭의 방향 d
		}
	}
	for (int i = 0; i < N; i++) {
		scanf("%d %d", &CMD[i].k, &CMD[i].c);
		if (CMD[i].c == 0) c_cnt++;	// c_cnt 개수만큼 조합돌려야 한다. 
	}
	memcpy(d_tmp, board, sizeof(board));	// 원본맵 백업용
}


void put_block(int type, int col)	// 블록의 종류, 블록이 떨어질 위치
{
	int row = 200;

	while (1) {
		if (board[row][col] == 0) break;
		row--;
	}
	board[row][col] = type;
	//printf("%d %d %d\n", row, col, type);
}


int chk_crush()
{
	int score = 0;

	for (int i = 200; i >= 1; i--) {
		V.clear();
		for (int j = 1; j <= 4; j++) {
			if (board[i][j] != 0) V.push_back({ i, j });
		}
		int size = V.size();
		if (size > 0 && size < 4) continue;
		if (V.size() == 4) {
			for (_vt v : V) {
				board[v.x][v.y] = 0;
			}
			score++;
		}
	}
	return score;
}


void gravity()
{
	std::queue<int> Q;

	for (int j = 1; j <= 4; j++) {
		for (int i = 200; i >= 1; i--) {
			if (board[i][j] != 0) {
				Q.push(board[i][j]);
				board[i][j] = 0;
			}
		}
		int row = 200;
		while (!Q.empty()) {
			board[row][j] = Q.front();
			Q.pop();
			row--;
		}
	}
}

void move_block()
{
	memset(tmp, 0, sizeof(tmp));

	// dir
	// // 0 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 = 200; i >= 1; i--) {
		for (int j = 1; j <= 4; j++) {
			if (board[i][j] != 0) {
				int num = board[i][j];
				for (int p = 1; p <= 8; p++) {
					int nx = i + dir_x[lookup[num][p]];
					int ny = j + dir_y[lookup[num][p]];

					if (nx < 1 || nx > 200 || ny < 1 || ny > 4) continue;
					
					if (tmp[nx][ny] == 0) tmp[nx][ny] = num;
					else if (tmp[nx][ny] > board[i][j]) tmp[nx][ny] = num;
					break;
				}
			}
		}
	}
	memcpy(board, tmp, sizeof(tmp));
}




int simulation()
{
	int num = 0;
	int total = 0;

	for (int i = 0; i < N; i++) {
		if (CMD[i].c != 0) put_block(CMD[i].k, CMD[i].c);
		else if (CMD[i].c == 0) {
			put_block(CMD[i].k, choice[num]);
			num++;
		}
		int score = chk_crush();
		total += score;
		gravity();
		move_block();
		gravity();
		total += chk_crush();
		gravity();
	}
	//debug();
	return total;
}


void DFS(int n)
{
	if (n == c_cnt) {
		int score = simulation();
		if (ans < score) ans = score;
		memcpy(board, d_tmp, sizeof(board));
		return;
	}


	for (int j = 1; j <= 4; j++) {	// 1번열부터 4번열까지 
		choice[n] = j;
		DFS(n + 1);
	}
}



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

문제 설명이 그지같아서 이해하기가 다소 어려워서 문제 설명 가장 마지막 줄에 summary를 보고 로직을 짰다. 

 

// 총 n번의 시행마다 블럭이 주어지고, 

1. c가 0인 경우에는 해당 블럭이 떨어질 위치가 정해지지 않은 것이므로 DFS를 돌려서 모든 경우의 수를 탐색해 보아야 한다. 

이때 열의 개수는 4개이고 (1열~4열) c는 최대 4개까지 있는데, 이때 순서가 중요하고 중복이 허용되므로 중복순열을 사용해야 한다.

 

2. c를 다 정했다면 시뮬레이션을 돌려준다. 

만약 c가 0이 아닌 경우에는 input 받은 열에 그대로 블럭을 떨어트려준다. 

만약 c가 0이면 DFS를 통해 구한 열에 블럭을 떨어트려 준다. 

 

3. 가장 아래 격자칸부터 터뜨릴 블럭이 있는지 확인한다. 

문제에서 4개의 열에 모두 블럭이 있으면 터트릴 수 있다고 했으므로 V.size() == 4일때만 해당 자리를 0으로 만들어 주고 score 변수를 증가시켜 주었다. 

 

// 이 블럭이 중력에 의해 떨어진 뒤 점수를 얻게 되고, 

4. 터트린 블럭이 있든 없든 gravity() 함수를 실행시켜 모든 블럭을 아래로 내려준다. 

 

// 각 블럭들이 주어진 우선순위에 맞춰 이동하게 한 뒤

5. 처음에 input 받았던 lookup 테이블에 저장된 대로 이동시켜 준다. 

만약 tmp[nx][ny]가 0이 아니라면, 해당 자리에 이미 다른 블럭이 위치한 것이므로 숫자를 비교해 더 작은 수로 바꿔준다. 

 

// 다시 중력에 의해 떨어져 점수를 얻게되는 과정

6. gravity() 함수를 또 실행해준 후, 얻어지는 점수가 있는지 chk_crush() 함수를 통해 확인한다. 이후 다시 gravity() 함수를 통해 모든 블럭을 아래로 내려준다. 

 

특이했던 것은 보통 문제들이 "점수를 내면 => 중력 작용하고 => 이동한다" 이런식인데, 이 문제는 블럭이 한 개 주어질 때 마다 모든 과정이 실행되어야 했다. 

이전에 풀었던 문제에 오리엔티드 되지 말고 문제를 잘 읽고 코드를 짜야겠다고 다시 한 번 다짐..