캔디크러시사가 알고리즘 문제풀이 (19년_에스원 코딩교육 숙제)

책임님께서 내주신 숙제^_^ (8/21, 수요일까지)

 

​

<캔디크러시사가>

명환이와 진엽이는 캔디크러시사가 게임으로 저녁 내기를 하려고한다. 내기를 도와줄 게임을 만들어보자^^

 

​

게임 규칙은 이러하다.

1. 똑같은 캔디 4개가 모여 사각형을 이루면, 없어지는 동시에 1점을 획득한다.

예)

AA

AA

 

*4개 이상의 캔디가 여러 개 있을 시, 위->아래, 왼->오 순서로 없어진다.

예)

AA _ _

AA -> _ _

AA AA

 

AAA _ _A

AAA -> _ _A

​

2. 캔디가 없어진 자리를 위쪽 캔디가 내려와 채운다.

예)

DDDDDDDDDD D DDDDDDD

GGGGGGGGGG G GGGGGGG

AAAAAAAAAA -> ADDAAAAAAA

CCCCCCCCCC CGGCCCCCCC

BCCBBBBBBBB BAABBBBBBB

EEEEEEEEEEEEE EEEEEEEEEEE

 

3. 더 이상 없앨 수 있는 캔디가 없다면 게임을 종료한다.

 

A와 B 두 사람 중 누가 몇 점 차이로 이기는지 출력하라.

​

​

​

(입력)

첫째 줄에 N(5<=N<=100,000), 둘째 줄에 1, 셋째 줄에 1의 캔디정보, 넷째 줄에 2, 다섯째 줄에 2의 캔디정보가 주어진다. 캔디정보는 N개의 줄에 10개의 캔디로 맵이 주어진다. 캔디 종류는 A~J 중 하나이다.

 

(출력)

첫째 줄에 이긴 사람, 둘째 줄에 점수 차를 출력하라. 비길 시에는 0을 출력한다.

 

예제 입력1

-------------------------

5

1

DDDDDDDDDD

GGGGGGGGGG

AAAAAAAAAA

CCCCCCCCCC

BCCBBBBBBB

2

DDDDDDDDDD

GGGGGGGGGG

AAAAAAAAAA

CCCCCCCCCC

BBBBBBBBBB

 

예제 출력1

------------------------

1

1

 

 

예제 입력2

-------------------------

6

1

DDDDDDDDDD

GGGGGGGGGG

AAAAAAAAAA

CCCCCCCCCC

BCCBBBBBBB

EEEEEEEEEE

2

DDDDDDDDDD

GGGGGGGGGG

AAAAAAAAAA

CCCCCCCCCC

BCCBBBBBBB

EEEEEEEEEE

 

예제 출력2

------------------------

0

 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <queue>
using namespace std;

/*
2019.08.19 김진엽
*/

/*
숙제^_ ^ (8 / 21, 수요일까지)

1. 똑같은 캔디 4개가 모여 사각형을 이루면, 없어지는 동시에 1점을 획득한다.
* 4개 이상의 캔디가 여러 개 있을 시, 위->아래, 왼->오 순서로 없어진다.
2. 캔디가 없어진 자리를 위쪽 캔디가 내려와 채운다.
3. 더 이상 없앨 수 있는 캔디가 없다면 게임을 종료한다.

A와 B 두 사람 중 누가 몇 점 차이로 이기는지 출력하라.

(입력)
첫째 줄에 N(10 <= N <= 100, 000),
둘째 줄에 1, 셋째 줄에 1의 캔디정보,
넷째 줄에 2, 다섯째 줄에 2의 캔디정보가 주어진다.
캔디정보는 N개의 줄에 10개의 캔디로 맵이 주어진다.
캔디 종류는 A~J 중 하나이다.


(출력)
첫째 줄에 이긴 사람,
둘째 줄에 점수 차를 출력하라.
*비길 시에는 0을 출력한다.
*/


char Arr1[100000][10];
char Arr2[100000][10];
bool check[100000][10];
int dx[4] = { 1, 0,-1, 0 };
int dy[4] = { 0,-1, 0, 1 };
int n, a, b;
int cnt = 0;
int cnt1 = 0;
int cnt2 = 0;
bool c;

void down(int y,int x, char tmparr[][10]) {
	for (int i = y; i >= 2; i--) {
		tmparr[i][x] = tmparr[i - 2][x];
		tmparr[i][x + 1] = tmparr[i - 2][x + 1];
		tmparr[i + 1][x] = tmparr[i - 1][x];
		tmparr[i + 1][x + 1] = tmparr[i - 1][x + 1];
	}
	tmparr[0][x] = tmparr[0][x + 1] = tmparr[1][x] = tmparr[1][x + 1] = 0;
	c = true;
}

void bfs(char arr1[][10]) {
	memset(check, false, sizeof(check));
	c = false;
	queue<pair<int, int>> q;
	q.push(make_pair(0, 0));
	pair<int, int> p;
	check[0][0] = true;
	while (!q.empty()) {
		p = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = p.first + dy[i];
			int nx = p.second + dx[i];

			if (nx < 10 && nx >= 0 && ny < n && ny >= 0 && check[ny][nx] == false) {
				if (arr1[ny][nx] == arr1[ny + 1][nx] && arr1[ny + 1][nx] == arr1[ny][nx + 1] && arr1[ny][nx + 1] == arr1[ny + 1][nx + 1]) {
					if (arr1[ny][nx] != 0 && arr1[ny + 1][nx] != 0 && arr1[ny][nx + 1] != 0 && arr1[ny + 1][nx + 1] != 0) {
						down(ny, nx,arr1); //4개 터트리고, 내려오기
						cnt++; //1점획득
					}
				}
				q.push(make_pair(ny, nx));
				check[ny][nx] = true;
			}
		}
	}
}

int main() {
	freopen("1.txt", "r", stdin);

	cin >> n;
	cin >> a;
	for (int i = 0; i < n; i++) {
		scanf("%s", Arr1[i]);
	}
	cin >> b;
	for (int i = 0; i < n; i++) {
		scanf("%s", Arr2[i]);
	}

	//////////////////////////////////

	while (1) {
		bfs(Arr1);
		if (c==false) break;
	}
	cnt1 = cnt;
	cnt = 0;
	while (1) {
		bfs(Arr2);
		if (c == false) break;
	}
	cnt2 = cnt;

	printf("\n");

	printf("--------------------------------------------\n");

	printf("<1 게임결과> \n");
	printf("\n");

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 10; j++) {
			printf("%c", Arr1[i][j]);
		}
		printf("\n");
	}
	printf("\n");
	printf("1의 점수: %d\n\n", cnt1);

	printf("--------------------------------------------\n");

	printf("<2 게임결과> \n");
	printf("\n");

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 10; j++) {
			printf("%c", Arr2[i][j]);
		}
		printf("\n");
	}
	printf("\n");
	printf("2의 점수: %d\n\n", cnt2);

	printf("--------------------------------------------\n");

	if (cnt1 > cnt2) {
		printf("1의 승리, 점수차: %d\n", cnt1 - cnt2);
	}
	else if (cnt1 < cnt2) {
		printf("2의 승리, 점수차: %d\n", cnt2 - cnt1);
	}
	else {
		printf("비겼습니다.\n");
	}
	printf("--------------------------------------------\n");

}

<1.txt>

​

7

1

EEEEEEEEEE

DDGDDDDDDD

GGGGGGGGGG

AAAGAAAAAA

CCCGCCCCCC

BCCBBBCCBB

EEEEEEEEEE

2

EEEEEEEEEE

DDDDDDGGDD

GGGGGGGGGG

AAAAAAAAAA

CCCGCCCCCC

BCCBBBCCEE

EEEEEEEEEE

​

 

---------------------------------------------------------------------------------------------------------------------

수정) 19.08.20

​

ny, nx가 0일때 자기 자리는 안터짐-> dx dy 0,0 추가

ny==1 일때 내려오는거 이상함 -> 수정

위,왼쪽 우선 -> 아래,왼쪽 우선 터지게 수정

 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>
#include <queue>
using namespace std;

/*
2019.08.20 김진엽
*/

/*
숙제^_ ^ (8 / 21, 수요일까지)

1. 똑같은 캔디 4개가 모여 사각형을 이루면, 없어지는 동시에 1점을 획득한다.
* 4개 이상의 캔디가 여러 개 있을 시, 위->아래, 왼->오 순서로 없어진다.
2. 캔디가 없어진 자리를 위쪽 캔디가 내려와 채운다.
3. 더 이상 없앨 수 있는 캔디가 없다면 게임을 종료한다.

A와 B 두 사람 중 누가 몇 점 차이로 이기는지 출력하라.

(입력)
첫째 줄에 N(10 <= N <= 100, 000),
둘째 줄에 1, 셋째 줄에 1의 캔디정보,
넷째 줄에 2, 다섯째 줄에 2의 캔디정보가 주어진다.
캔디정보는 N개의 줄에 10개의 캔디로 맵이 주어진다.
캔디 종류는 A~J 중 하나이다.


(출력)
첫째 줄에 이긴 사람,
둘째 줄에 점수 차를 출력하라.
*비길 시에는 0을 출력한다.
*/


char Arr1[100000][10];
char Arr2[100000][10];
bool check[100000][10];
int dx[5] = {0, 1, 0,-1, 0};
int dy[5] = {0, 0, 1, 0, -1};
int n, a, b;
int cnt = 0;
int cnt1 = 0;
int cnt2 = 0;
bool c;

void down(int y,int x, char tmparr[][10]) {
	for (int i = y; i >= 2; i--) {
		tmparr[i][x] = tmparr[i - 2][x];
		tmparr[i][x + 1] = tmparr[i - 2][x + 1];
		tmparr[i - 1][x] = tmparr[i - 3][x];
		tmparr[i - 1][x + 1] = tmparr[i - 3][x + 1];
	}
	tmparr[0][x] = tmparr[0][x + 1] = tmparr[1][x] = tmparr[1][x + 1] = 0;
	c = true;
}

void bfs(char arr1[][10]) {
	memset(check, false, sizeof(check));
	c = false;
	queue<pair<int, int>> q;
	q.push(make_pair(n-1, 0));
	pair<int, int> p;
	while (!q.empty()) {
		p = q.front();
		q.pop();
		for (int i = 0; i < 5; i++) { 
			int ny = p.first + dy[i];
			int nx = p.second + dx[i];

			if (nx < 10 && nx >= 0 && ny < n && ny >= 0 && check[ny][nx] == false) {
				if (arr1[ny][nx] == arr1[ny - 1][nx] && arr1[ny - 1][nx] == arr1[ny][nx + 1] && arr1[ny][nx + 1] == arr1[ny - 1][nx + 1]) {
					if (arr1[ny][nx] != 0 && arr1[ny - 1][nx] != 0 && arr1[ny][nx + 1] != 0 && arr1[ny - 1][nx + 1] != 0) {
						down(ny, nx,arr1); //4개 터트리고, 내려오기
						cnt++; //1점획득
					}
				}
				q.push(make_pair(ny, nx));
				check[ny][nx] = true;
			}
		}
	}
}

int main() {
	freopen("2.txt", "r", stdin);

	cin >> n;
	cin >> a;
	for (int i = 0; i < n; i++) {
		scanf("%s", Arr1[i]);
	}
	cin >> b;
	for (int i = 0; i < n; i++) {
		scanf("%s", Arr2[i]);
	}

	//////////////////////////////////

	while (1) {
		bfs(Arr1);
		if (c==false) break;
	}
	cnt1 = cnt;

	cnt = 0;

	while (1) {
		bfs(Arr2);
		if (c == false) break;
	}
	cnt2 = cnt;

	printf("\n");

	printf("--------------------------------------------\n");

	printf("<1 게임결과> \n");
	printf("\n");

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 10; j++) {
			printf("%c", Arr1[i][j]);
		}
		printf("\n");
	}
	printf("\n");
	printf("1의 점수: %d\n\n", cnt1);

	printf("--------------------------------------------\n");

	printf("<2 게임결과> \n");
	printf("\n");

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 10; j++) {
			printf("%c", Arr2[i][j]);
		}
		printf("\n");
	}
	printf("\n");
	printf("2의 점수: %d\n\n", cnt2);

	printf("--------------------------------------------\n");

	if (cnt1 > cnt2) {
		printf("1의 승리, 점수차: %d\n", cnt1 - cnt2);
	}
	else if (cnt1 < cnt2) {
		printf("2의 승리, 점수차: %d\n", cnt2 - cnt1);
	}
	else {
		printf("비겼습니다.\n");
	}
	printf("--------------------------------------------\n");

}