SWEA 5656 : 벽돌 깨기 (모의 SW 역량테스트)

 

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

 

삼성 A형 전체 링크

 

모의 SW 역량테스트 문제집

 

벽돌 깨기 링크

 

이후 설명 및 입/출력은 링크 참고

 

벽돌은 (1, 1)부터 입력을 받고 주변을 벽(-1)으로 만들어두자.

#define MAX (15 + 5)

int T, N, W, H;
int MAP[MAX][MAX];
int MINANS;

void input()
{
	scanf("%d %d %d", &N, &W, &H);

	for (int r = 0; r <= H + 1; r++)
		for (int c = 0; c <= W + 1; c++)
			MAP[r][c] = -1;
	
	for (int r = 1; r <= H; r++)
		for (int c = 1; c <= W; c++)
			scanf("%d", &MAP[r][c]);
}

 

매 tc마다 input을 받고, 남은 벽돌의 최소 개수인 MINANS를 초기화하고 DFS를 실행한다.

int main(void)
{
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++)
	{
		input();

		MINANS = 0x7fff0000;

		DFS(0, MAP);
		
		printf("#%d %d\n", tc, MINANS);
	}

	return 0;
}

---

한 번 벽돌을 부순 곳에서 다시 벽돌을 부술 수 있으므로, 경우의 수는 W^N이 된다. 

중복 순열을 참고해서 DFS를 구성하였다.

 

모든 column에 대해 Level이 N이 될 때 까지,

map을 copy, crash, move를 하고, 다음 DFS에 변경된 map을 넘긴다.

 

마지막 L에서 남은 벽돌을 세고 MINANS를 갱신한다.

void DFS(int L, int map[MAX][MAX])
{

	if (L == N)
	{
		int tmp = count(map);
		if (tmp < MINANS) MINANS = tmp;

		return;
	}

	for (int col = 1; col <= W; col++)
	{
		int sr = check(col, map);
		if (sr == -1)
		{
			DFS(L + 1, map);
			continue;
		}

		int tmpMAP[MAX][MAX] = { 0 };

		copy(tmpMAP, map);
		crash(sr, col, tmpMAP);
		move(tmpMAP);
		
		DFS(L + 1, tmpMAP);
	}
}

---

crash도 연쇄적으로 일어나기 때문에 재귀함수로 만든다.

 

먼저 check함수에서 column에 대해 가장 위에 있는 벽돌의 row를 return하도록 만든다.

int check(int column, int map[MAX][MAX])
{
	for (int row = 1; row <= H; row++)
		if (map[row][column]) return row;

	return -1;
}

해당 row가 없으면 -1을 return해서 map을 변형하지 않고, 다음 DFS로 넘어갈 수 있다.

 

row가 있는 경우, (r, c) 그리고 map을 넘겨받아 벽돌을 부순다.

벽돌에 적힌 size만큼 계속 부숴야하고, dr, dc 배열을 이용해 4방향 모두 부순다.

벽돌을 부수면서 벽을 만나면 종료한다.

벽이 0인 경우는 다시 crash할 필요 없으므로 MAP[r][c] > 0인 경우만 crash를 호출한다.

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

void crash(int sr, int sc, int map[MAX][MAX])
{
	int size = map[sr][sc];
	
	map[sr][sc] = 0;

	for (int dir = 0; dir < 4; dir++)
	{
		for (int i = 1; i < size; i++)
		{
			int nr, nc;

			nr = sr + dr[dir] * i;
			nc = sc + dc[dir] * i;
			
			if (MAP[nr][nc] == -1) break; /* 벽인 경우 종료 */
			
			if (MAP[nr][nc] > 0) crash(nr, nc, map);
		}	
	}
}

 

crash가 종료되면 벽돌을 모두 아래로 내려야 한다.

먼저 column에 대해 row = H부터 시작하여 벽돌이 있는 경우 list에 순서대로 저장한다.

저장하면서 map은 0으로 만들어둔다.

그리고 다시 list를 보고 map[H][column]부터 1칸씩 벽돌을 만들면 벽돌의 이동이 완료된다.

void move(int map[MAX][MAX])
{
	for (int c = 1; c <= W; c++)
	{
		int list[MAX] = { 0 };
		int lcnt = 0;

		for (int r = H; r >= 1; r--)
		{
			if (map[r][c])
			{
				list[lcnt++] = map[r][c];
				map[r][c] = 0;
			}
		}

		int sr = H;
		for (int l = 0; l < lcnt; l++) map[sr--][c] = list[l];
	}
}

 

남은 벽돌은 단순히 map을 보고 counting하면 되므로, 최종 코드를 참고하자.

#include <stdio.h>

#define MAX (15 + 5)

int T, N, W, H;
int MAP[MAX][MAX];
int MINANS;

void input()
{
	scanf("%d %d %d", &N, &W, &H);

	for (int r = 0; r <= H + 1; r++)
		for (int c = 0; c <= W + 1; c++)
			MAP[r][c] = -1;
	
	for (int r = 1; r <= H; r++)
		for (int c = 1; c <= W; c++)
			scanf("%d", &MAP[r][c]);
}

void output(int map[MAX][MAX])
{
	for (int r = 1; r <= H; r++)
	{
		for (int c = 1; c <= W; c++)
			printf("%d ", map[r][c]);
		putchar('\n');
	}
	putchar('\n');
}

void copy(int dest[MAX][MAX], int src[MAX][MAX])
{
	for (int r = 0; r <= H + 1; r++)
		for (int c = 0; c <= W + 1; c++)
			dest[r][c] = src[r][c];
}

int check(int column, int map[MAX][MAX])
{
	for (int row = 1; row <= H; row++)
		if (map[row][column]) return row;

	return -1;
}

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

void crash(int sr, int sc, int map[MAX][MAX])
{
	int size = map[sr][sc];
	
	map[sr][sc] = 0;

	for (int dir = 0; dir < 4; dir++)
	{
		for (int i = 1; i < size; i++)
		{
			int nr, nc;

			nr = sr + dr[dir] * i;
			nc = sc + dc[dir] * i;
			
			if (MAP[nr][nc] == -1) break; /* 벽인 경우 종료 */
			
			if (MAP[nr][nc] > 0) crash(nr, nc, map);
		}	
	}
}

void move(int map[MAX][MAX])
{
	for (int c = 1; c <= W; c++)
	{
		int list[MAX] = { 0 };
		int lcnt = 0;

		for (int r = H; r >= 1; r--)
		{
			if (map[r][c])
			{
				list[lcnt++] = map[r][c];
				map[r][c] = 0;
			}
		}

		int sr = H;
		for (int l = 0; l < lcnt; l++) map[sr--][c] = list[l];
	}
}

int count(int map[MAX][MAX])
{
	int sum = 0;
	for (int r = 1; r <= H; r++)
		for (int c = 1; c <= W; c++)
			sum += !!map[r][c];

	return sum;
}

void DFS(int L, int map[MAX][MAX])
{

	if (L == N)
	{
		int tmp = count(map);
		if (tmp < MINANS) MINANS = tmp;

		return;
	}

	for (int col = 1; col <= W; col++)
	{
		int sr = check(col, map);
		if (sr == -1)
		{
			DFS(L + 1, map);
			continue;
		}

		int tmpMAP[MAX][MAX] = { 0 };

		copy(tmpMAP, map);
		crash(sr, col, tmpMAP);
		move(tmpMAP);
		
		DFS(L + 1, tmpMAP);
	}
}

int main(void)
{
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++)
	{
		input();

		MINANS = 0x7fff0000;

		DFS(0, MAP);
		
		printf("#%d %d\n", tc, MINANS);
	}

	return 0;
}

---

count함수에서 sum += !!map[r][c]를 이용하였는데, 변수 앞에 !!를 해주면 1보다 큰 경우는 1로, 0이면 0이된다.

ex) a = 5 → !a = 0 → !!a = 1 / b = 0 → !b = 1 → !!b = 0

 

MAP에 적힌 수와 상관없이 0보다 큰 값을 셀 때 유용한 방법이다.