알고리즘 문제 풀기

백준 : 4358번 생태학 ,17837번 새로운 게임2

studying develop 2020. 1. 25. 16:54

4358번 생태학

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<malloc.h>
#include<vector>
#include<algorithm>
#include<string.h>
#include<string>
#include<map>


using namespace std;

map<string, int> m;

//종의 갯수를 빠르게 세기위한 트라이
struct Trie {
	bool finish;
	int cnt = 0;
	Trie* next[200];
	Trie() : finish(false) {
		memset(next, 0, sizeof next);
	}
	~Trie() {
		for (int i = 0; i < 200; i++) {
			if (next[i])
				delete next[i];
		}
	}
	void insert(const char* key) {
		if (*key == '\0') {
			finish = true;
			cnt++;
		}
		else {
			int curr = *key;
			//int curr = *key -'A';
			if (next[curr] == NULL) {
				next[curr] = new Trie();
			}
			next[curr]->insert(key + 1);
		}
	}
	Trie* find(const char* key) {
		if (*key == '\0') return this;

		int curr = *key;
		//int curr = *key - 'A';
		if (next[curr] == NULL) return NULL;

		return next[curr]->find(key + 1);
	}
	int findCnt(const char* key) {
		if (*key == '\0') return this->cnt;

		int curr = *key;
		//int curr = *key - 'A';
		if (next[curr] == NULL) return NULL;

		return next[curr]->findCnt(key + 1);
	}

};

struct node {
	char arr[33];
	node* next;
};

struct HashMap {
	node* hash[1001] = { NULL };
	int hashMax = 1001;
	int size = 0;

	int getHash(const char *str) {
		int ans = 0;
		int index = 0;
		while (1) {
			if (str[index] == '\0') {
				return ans % hashMax;
			}
			ans += str[index];
			index++;
		}
	}

	void add(const char * str) {
int hashIndex = getHash(str);
node* newNode = new node;

int index = 0;
//새노드에 값 할당.
while (1) {
	newNode->arr[index] = str[index];

	if (str[index] == '\0')
		break;
	index++;
}
newNode->next = NULL;

//이어 붙이기.
if (hash[hashIndex] == NULL)
{
	hash[hashIndex] = newNode;
}
else {
	node* cur = hash[hashIndex];
	while (1) {
		if (cur != NULL) {
			cur = cur->next;
		}
		else {
			cur = newNode;
			//이 부분을 뺴먹었었다.
			break;
		}
	}
}
size++;
	}//add

	bool stringCmp(const char* str1, const char* str2) {
		int in1 = 0, in2 = 0;
		while (1) {
			if (str1[in1] != str2[in2]) {
				return false;
			}

			if (str1[in1] == '\0' && str2[in2] == '\0')
				return true;
			else if (str1[in1] == '\0' || str2[in2] == '\0')
				return false;
			in1++;
			in2++;
		}
	}

	bool find(const char* str) {
		int hashIndex = getHash(str);

		if (hash[hashIndex] == NULL)
		{
			return false;
		}
		else {
			node* cur = hash[hashIndex];
			while (1) {
				if (cur != NULL) {
					if (stringCmp(str, cur->arr)) {
						return true;
					}
					cur = cur->next;
				}
				else {
					return false;
				}
			}
		}
	}
};



HashMap userHash;
Trie trie;
vector<string> vec;
char arr[33];
char origin[33];
int sumCnt = 0;

void stdinFunc() {
	//freopen("input.txt", "r", stdin);
	int flag = 0;

	string s;

	while (getline(cin, s)) {
		strcpy(arr, s.c_str());
//		trie.insert(arr);
		sumCnt++;
		/*
		if (userHash.find(arr) == false) {
			userHash.add(arr);
			vec.push_back(arr);
		}
		*/
		if (m.count(s) == 0){
			m.insert(make_pair(s, 1));
			vec.push_back(s);
		}
		else if (m.find(s)->second >= 1) {
			m[s] += 1;
		}

	}

}

int main() {
	/*
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	*/
	stdinFunc();

	sort(vec.begin(), vec.end());

	cout.precision(4);
	cout << fixed;

	for (int i = 0; i < vec.size(); i++) {
		string str = vec[i];


		cout << str << " " << 100 * ((double)m.find(str)->second / sumCnt) << "\n";
		//printf("%s %0.4lf\n", str.c_str(),100*((double) trie.findCnt(str.c_str()) / (double)sumCnt));
	}

	return 0;
}

 

밑에는 라이브러리 없이 풀려다가 실패해서 그냥 라이브러리 일단 사용하고 푼 코드입니다.

 

음 트라이에 넣을때 공백을 제거하고 대문자로 변환해서 넣는 방법을 선택했다. 그거보다 그냥 tri를 next[200]으로 아스키 코드 범위를 커버했다. 깊이가 30까지라 메모리 한도가 걱정된다.

 

그리고 종을 정렬되서 저장하려고 한다. -> 해쉬를 사용해야 할것 같다. 해쉬를 구현해서 map의 insert, find기능을 구현했다.

 

음 문자열간의 비교를 못해서 리스트에서 퀵소트를 구현하지 못했다. 그리고 퀵소트 구현시 노드의 next를 변화시켜서 정렬하는 것 인지, 값을 swap해서 정렬하는 것인지 잘 모르겠었다.

 

몇개는 0으로 나온다. 트라이에서 갯수가 제대로 안세어진다. 왜그러지? 공백 문제인가.

 

그리고 printf 사용시 string의 출력과 %0.4f 출력이 제대로 안됬다. 왜그런지 모르겠다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<malloc.h>
#include<vector>
#include<algorithm>
#include<string>

using namespace std;

//종의 갯수를 빠르게 세기위한 트라이
struct Trie {
	bool finish;
	int cnt = 0;
	Trie* next[200];
	Trie() : finish(false) {
		memset(next, 0, sizeof next);
	}
	~Trie() {
		for (int i = 0; i < 26; i++) {
			if (next[i])
				delete next[i];
		}
	}
	void insert(const char* key) {
		if (*key == '\0') {
			finish = true;
			cnt++;
		}
		else {
			int curr = *key - 'A';
			if (next[curr] == NULL) {
				next[curr] = new Trie();
			}
			next[curr]->insert(key + 1);
		}
	}
	Trie* find(const char* key) {
		if (*key == '\0') return this;
		
		int curr = *key - 'A';
		if (next[curr] == NULL) return NULL;
		
		return next[curr]->find(key + 1);
	}
	int findCnt(const char* key) {
		if (*key == '\0') return this->cnt;

		int curr = *key - 'A';
		if (next[curr] == NULL) return NULL;

		return next[curr]->findCnt(key + 1);
	}

};

struct node {
	char arr[33];
	node* next;
};

struct HashMap {
	node* hash[1001] = { NULL };
	int hashMax = 1001;
	int size = 0;

	int getHash(const char *str) {
		int ans = 0;
		int index = 0;
		while (1) {
			if (str[index] == '\0') {
				return ans%hashMax;
			}
			ans += str[index];
			index++;
		}
	}

	void add(const char * str) {
		int hashIndex = getHash(str);
		node* newNode = new node;
		
		int index = 0;
		//새노드에 값 할당.
		while (1) {
			newNode->arr[index] = str[index];

			if (str[index] == '\0')
				break;
			index++;
		}
		newNode->next = NULL;

		if (hash[hashIndex] == NULL)
		{
			hash[hashIndex] = newNode;
		}
		else {
			node* cur = hash[hashIndex];
			while (1) {
				if (cur != NULL) {
					cur = cur->next;
				}
				else {
					cur = newNode;
				}
			}
		}
		size++;
	}//add

	bool stringCmp(const char* str1, const char* str2) {
		int in1=0, in2 = 0;
		while (1) {
			if (str1[in1] != str2[in2]) {
				return false;
			}

			if (str1[in1] == '\0' && str2[in2] == '\0')
				return true;
			else if (str1[in1] == '\0' || str2[in2] == '\0')
				return false;
			in1++;
			in2++;
		}
	}

	bool find(const char* str) {
		int hashIndex = getHash(str);

		if (hash[hashIndex] == NULL)
		{
			return false;
		}
		else {
			node* cur = hash[hashIndex];
			while (1) {
				if (cur != NULL) {
					if (stringCmp(str, cur->arr)) {
						return true;
					}
					cur = cur->next;
				}
				else {
					return false;
				}
			}
		}
	}
};

struct linkedList {
	node* head=NULL;
	node * end=NULL;
	int size = 0;
	
	bool BehindIsBigger(const char* str1, const char* str2) {
		int in = 0;
		while (1) {
			if (str1[in] <= str2[in]) {
				continue;
			}
			else if (str1[in] > str2[in]) {
				return false;
			}

			if (str1[in] == '\0' && str2[in] == '\0')
				return true;
			else if (str1[in] == '\0' && str2[in] != '\0')
				return false;
			else if (str1[in] != '\0' && str2[in] == '\0')
				return true;
			in++;
		}
	}

	void add(const char* str) {
		node * newNode = new node;

		//새노드에 값 할당.
		int index = 0;
		while (1) {
			newNode->arr[index] = str[index];

			if (str[index] == '\0')
				break;
			index++;
		}
		newNode->next = NULL;

		if (head == NULL) {
			head = newNode;
			end = newNode;
		}
		else {
			end->next = newNode;
			end = newNode;
		}
		size++;
	}

	void sort() {
		;
	}
};

HashMap userHash;
linkedList userList;
Trie trie;
vector<string> vec;
char arr[33];
char origin[33];
int sumCnt = 0;

void stdinFunc() {
	freopen("input.txt", "r", stdin);
	int flag = 0;
	while (1)
	{
		int index = 0;

		while (1) {
			char x;
			if (scanf("%c", &x) != 1 ) {
				if (index != 0) {
					arr[index] = '\0';
					trie.insert(arr);

					if (userHash.find(arr) == false) {
						userHash.add(arr);
//						userList.add(arr);
						vec.push_back(arr);
						sumCnt++;
					}
				}
				break;
			}
			flag = 1;

			arr[index] = x;
			if (x == '\n') {
				arr[index] = '\0';
				trie.insert(arr);

				if (userHash.find(arr) == false) {
					userHash.add(arr);
	//				userList.add(arr);
					vec.push_back(arr);
					sumCnt++;
				}

				break;
			}
			index++;

		}//while

		if (flag == 0) {
			break;
		}
		flag = 0;
	}

		/*
	while (1)
	{
		int index = 0;

		while (1) {
			
			char x;
			if (scanf("%c", &x) != 1)
				break;

			flag = 1;

			if ('a' <= x && x <= 'z') {
				origin[index] = x;
				x += 'A' - 'a';
				arr[index] = x;
				
			}
			else if( 'A'<=x && x<='Z') {
				origin[index] = x;
				arr[index] = x;
			}
			//대문자로 변환한 값이 arr에 저장된다.
			else if (x == '\n') {
				arr[index] = '\0';
				origin[index] = '\0';
				trie.insert(arr);
				break;
			}

			if( x != ' ')
				index++;

		}
		if (flag == 0) {
			break;
		}
		flag = 0;
	}
	*/
}

int main() {

	//ios_base().sync_with_stdio(false);

	stdinFunc();

	sort(vec.begin(), vec.end());

	for (int i = 0; i < vec.size(); i++) {
		string str = vec[i];
		cout << str << " " << (float)trie.findCnt(str.c_str()) / (float)sumCnt << "\n";
		//printf("%s %0.4f\n", str,(float) trie.findCnt(str.c_str()) / (float)sumCnt);
	}


	/*
	node* cur = userList.head;
	
	while (1) {
		if (cur != NULL) {
			printf("%s : %d\n",cur->arr,trie.findCnt(cur->arr));
			cur = cur->next;
		}
		else {
			break;
		}
	}
	*/


	/*
	char tmp[33] = "Ash";
	printf("%d\n",trie.findCnt(tmp));
	*/
	/*
	while (1)
	{
	int index = 0;

	while (1) {

	char x;
	if (scanf("%c", &x) != 1)
	break;

	flag = 1;

	if ('a' <= x && x <= 'z') {
	origin[index] = x;
	x += 'A' - 'a';
	arr[index] = x;

	}
	else if( 'A'<=x && x<='Z') {
	origin[index] = x;
	arr[index] = x;
	}
	//대문자로 변환한 값이 arr에 저장된다.
	else if (x == '\n') {
	arr[index] = '\0';
	origin[index] = '\0';
	trie.insert(arr);
	break;
	}

	if( x != ' ')
	index++;

	}
	if (flag == 0) {
	break;
	}
	flag = 0;
	}
	*/
	return 0;
}

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<malloc.h>
#include<vector>
#include<algorithm>
#include<string.h>

using namespace std;

//종의 갯수를 빠르게 세기위한 트라이
struct Trie {
	bool finish;
	int cnt = 0;
	Trie* next[200];
	Trie() : finish(false) {
		memset(next, 0, sizeof next);
	}
	~Trie() {
		for (int i = 0; i < 26; i++) {
			if (next[i])
				delete next[i];
		}
	}
	void insert(const char* key) {
		if (*key == '\0') {
			finish = true;
			cnt++;
		}
		else {
			int curr = *key - 'A';
			if (next[curr] == NULL) {
				next[curr] = new Trie();
			}
			next[curr]->insert(key + 1);
		}
	}
	Trie* find(const char* key) {
		if (*key == '\0') return this;
		
		int curr = *key - 'A';
		if (next[curr] == NULL) return NULL;
		
		return next[curr]->find(key + 1);
	}
	int findCnt(const char* key) {
		if (*key == '\0') return this->cnt;

		int curr = *key - 'A';
		if (next[curr] == NULL) return NULL;

		return next[curr]->findCnt(key + 1);
	}

};

struct node {
	char arr[33];
	node* next;
};

struct HashMap {
	node* hash[1001] = { NULL };
	int hashMax = 1001;
	int size = 0;

	int getHash(const char *str) {
		int ans = 0;
		int index = 0;
		while (1) {
			if (str[index] == '\0') {
				return ans%hashMax;
			}
			ans += str[index];
			index++;
		}
	}

	void add(const char * str) {
		int hashIndex = getHash(str);
		node* newNode = new node;
		
		int index = 0;
		//새노드에 값 할당.
		while (1) {
			newNode->arr[index] = str[index];

			if (str[index] == '\0')
				break;
			index++;
		}
		newNode->next = NULL;

		if (hash[hashIndex] == NULL)
		{
			hash[hashIndex] = newNode;
		}
		else {
			node* cur = hash[hashIndex];
			while (1) {
				if (cur != NULL) {
					cur = cur->next;
				}
				else {
					cur = newNode;
				}
			}
		}
		size++;
	}//add

	bool stringCmp(const char* str1, const char* str2) {
		int in1=0, in2 = 0;
		while (1) {
			if (str1[in1] != str2[in2]) {
				return false;
			}

			if (str1[in1] == '\0' && str2[in2] == '\0')
				return true;
			else if (str1[in1] == '\0' || str2[in2] == '\0')
				return false;
			in1++;
			in2++;
		}
	}

	bool find(const char* str) {
		int hashIndex = getHash(str);

		if (hash[hashIndex] == NULL)
		{
			return false;
		}
		else {
			node* cur = hash[hashIndex];
			while (1) {
				if (cur != NULL) {
					if (stringCmp(str, cur->arr)) {
						return true;
					}
					cur = cur->next;
				}
				else {
					return false;
				}
			}
		}
	}
};

struct linkedList {
	node* head=NULL;
	node * end=NULL;
	int size = 0;
	
	bool BehindIsBigger(const char* str1, const char* str2) {
		int in = 0;
		while (1) {
			if (str1[in] <= str2[in]) {
				continue;
			}
			else if (str1[in] > str2[in]) {
				return false;
			}

			if (str1[in] == '\0' && str2[in] == '\0')
				return true;
			else if (str1[in] == '\0' && str2[in] != '\0')
				return false;
			else if (str1[in] != '\0' && str2[in] == '\0')
				return true;
			in++;
		}
	}

	void add(const char* str) {
		node * newNode = new node;

		//새노드에 값 할당.
		int index = 0;
		while (1) {
			newNode->arr[index] = str[index];

			if (str[index] == '\0')
				break;
			index++;
		}
		newNode->next = NULL;

		if (head == NULL) {
			head = newNode;
			end = newNode;
		}
		else {
			end->next = newNode;
			end = newNode;
		}
		size++;
	}

	void sort() {
		;
	}
};

HashMap userHash;
linkedList userList;
Trie trie;
vector<string> vec;
char arr[33];
char origin[33];
int sumCnt = 0;

void stdinFunc() {
	freopen("input.txt", "r", stdin);
	int flag = 0;
	while (1)
	{
		int index = 0;
		sumCnt++;
		while (1) {
			char x;
			if (scanf("%c", &x) != 1 ) {
				if (index != 0) {
					arr[index] = '\0';
					trie.insert(arr);

					if (userHash.find(arr) == false) {
						userHash.add(arr);
//						userList.add(arr);
						vec.push_back(arr);

					}
				}
				break;
			}
			flag = 1;

			arr[index] = x;
			if (x == '\n') {
				arr[index] = '\0';
				trie.insert(arr);

				if (userHash.find(arr) == false) {
					userHash.add(arr);
	//				userList.add(arr);
					vec.push_back(arr);
				}

				break;
			}
			index++;

		}//while

		if (flag == 0) {
			break;
		}
		flag = 0;
	}

		/*
	while (1)
	{
		int index = 0;

		while (1) {
			
			char x;
			if (scanf("%c", &x) != 1)
				break;

			flag = 1;

			if ('a' <= x && x <= 'z') {
				origin[index] = x;
				x += 'A' - 'a';
				arr[index] = x;
				
			}
			else if( 'A'<=x && x<='Z') {
				origin[index] = x;
				arr[index] = x;
			}
			//대문자로 변환한 값이 arr에 저장된다.
			else if (x == '\n') {
				arr[index] = '\0';
				origin[index] = '\0';
				trie.insert(arr);
				break;
			}

			if( x != ' ')
				index++;

		}
		if (flag == 0) {
			break;
		}
		flag = 0;
	}
	*/
}

int main() {

	//ios_base().sync_with_stdio(false);

	stdinFunc();

	sort(vec.begin(), vec.end());
	sumCnt--;
	for (int i = 0; i < vec.size(); i++) {
		string str = vec[i];
		cout << str << " " << 100*((float)trie.findCnt(str.c_str()) / (float)sumCnt) << "\n";
	//	printf("%s %0.4f\n", str,(float) trie.findCnt(str.c_str()) / (float)sumCnt);
	}


	/*
	node* cur = userList.head;
	
	while (1) {
		if (cur != NULL) {
			printf("%s : %d\n",cur->arr,trie.findCnt(cur->arr));
			cur = cur->next;
		}
		else {
			break;
		}
	}
	*/


	/*
	char tmp[33] = "Ash";
	printf("%d\n",trie.findCnt(tmp));
	*/
	/*
	while (1)
	{
	int index = 0;

	while (1) {

	char x;
	if (scanf("%c", &x) != 1)
	break;

	flag = 1;

	if ('a' <= x && x <= 'z') {
	origin[index] = x;
	x += 'A' - 'a';
	arr[index] = x;

	}
	else if( 'A'<=x && x<='Z') {
	origin[index] = x;
	arr[index] = x;
	}
	//대문자로 변환한 값이 arr에 저장된다.
	else if (x == '\n') {
	arr[index] = '\0';
	origin[index] = '\0';
	trie.insert(arr);
	break;
	}

	if( x != ' ')
	index++;

	}
	if (flag == 0) {
	break;
	}
	flag = 0;
	}
	*/
	return 0;
}

비주얼 스튜디오로 하면 답은 나오는데 돌리면 런타임 에러가 뜬다..; 

 

트라이에 자료구조 크기가 너무 큰가? 문자열 길이가 30이면 200^30 아닌가... 그렇다고 26^30은되는건가? 이것도 이상한데 트라이의 크기 제한은 어떻게 결정되지 ....?

 

그냥 문자 갯수만큼 아닌가??

 

 

 

새로운 게임2

삼성 a형도 봐야될 수 도 있으니까 리프레쉬하는 느낌으로 푸렁봤는데 1시간 걸렸는데 못 풀었다. ㅋㅋ

 

문제 잘못이해해서 해맨 부분이 있는데

 

턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동한다. 이거랑

 

  • 파란색인 경우에는 A번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 한 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 방향만 반대로 바꾼다.
  • 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.

이거다 반대 방향으로 돌리고 이동한다는 건데 이동을 안시켰다.....아

 

 

그리고 이 말도 좀 햇갈린다.

 

턴이 진행되던 중에 말이 4개 쌓이는 순간 게임이 종료된다. 새로 이동한 곳만 4개 쌓여야 되는건가 아니면 원래 있던 곳도 4개여도 되는건가?

 

음 일단 고친건 Red,White,Blue enum 선언을 잘못했었고, 블루에서 반대로 이동했을때 화이트인 경우랑 블루인 경우 분리해서 처리했어야 했다.

 

아 그리고 배열이 1,1 ~ N,N인데 0,0 부터 했다.;

 

고쳐 준 부분이

a 벡터의 크기가 변하는데 size 대신에 a.size()로 했다....

근데 틀렸다. 91프로 까지 맞긴 하는데... 어디서 틀린걸까 a형을 따면 뭐하나 맨날 이렇게 틀린다.

 

	//위에 놈들은 제거 0 1 2 3 4
	int size = a.size();
	for (int i = 0; i < size - pos; i++) {
		a.pop_back();
	}
#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct chess {
	int r, c;
	int dir;
};
int arr[13][13];
vector<int> stacked[13][13];

int N, K;
vector<chess>vec;

enum {
	White = 0,
	Blue = 2,
	Red = 1
};


int dir_r[5] = { 0,0,0,-1,1 };
int dir_c[5] = { 0,1,-1,0,0 };

void ridOfElem(int chessInd, vector<int>&chesses) {
	int pos;
	for (int i = 0; i < chesses.size(); i++) {
		if (chesses[i] == chessInd)
		{
			pos = i;
			break;
		}
	}
	chesses.erase(chesses.begin() + pos);
	return;
}

void changeDir(int chessInd) {
	int dir = vec[chessInd].dir;
	int opposite;

	if (dir == 1)
		opposite = 2;
	else if (dir == 2) 
		opposite = 1;

	else if (dir == 3)
		opposite = 4;
	else if (dir == 4)
		opposite = 3;

	vec[chessInd].dir = opposite;
	return;
}

void moveAtoB(vector<int>&a, vector<int>&b,int chessInd,int nr,int nc) {
	int pos;
	
	for (int i = 0; i < a.size(); i++) {
		if (a[i] == chessInd)
		{
			pos = i;
			break;
		}
	}

	//위에 놈들도 위치 갱신후 이동
	for (int i = pos; i < a.size(); i++) {
		vec[a[i]].r = nr;
		vec[a[i]].c = nc;
		b.push_back(a[i]);
	}
	
	//위에 놈들은 제거 0 1 2 3 4
	int size = a.size();
	for (int i = 0; i < size - pos; i++) {
		a.pop_back();
	}

}

bool moveChess(int chessInd) {
	int nr, nc;
	int r, c;
	int dir;
	dir = vec[chessInd].dir;
	r = vec[chessInd].r;
	c = vec[chessInd].c;
	nr = r + dir_r[dir];
	nc = c + dir_c[dir];
	//범위 밖인 경우. 방향을 반대로 돌리고 이동하려 해본다.
	if (nr <1 || nr > N || nc <1 || nc > N) {
		changeDir(chessInd);
		dir = vec[chessInd].dir;
		nr = r + dir_r[dir];
		nc = c + dir_c[dir];

		if ((nr <1 || nr > N || nc <1 || nc > N) || arr[nr][nc] == Blue)
			return false;

		if (arr[nr][nc] == White) {
			moveAtoB(stacked[r][c], stacked[nr][nc], chessInd, nr, nc);
		}
		else if (arr[nr][nc] == Red) {
			int size = stacked[nr][nc].size();
			moveAtoB(stacked[r][c], stacked[nr][nc], chessInd, nr, nc);
			reverse(stacked[nr][nc].begin() + size, stacked[nr][nc].end());

		}


	}

	//이동하려는 곳이 흰색인 경우. 현재 벡터에서 제거하고 이동한다.
	else if (arr[nr][nc] == White) {
		//ridOfElem(chessInd, stacked[r][c]);
		//stacked[nr][nc].push_back(chessInd);
		moveAtoB(stacked[r][c], stacked[nr][nc], chessInd,nr,nc);

	}
	//빨강색인 경우. 벡터 전체를 이동후,이동한! 벡터만 뒤집어야 한다.
	//이게 아니라 자기 위의 벡터를 이동시키는 것이다.
	else if (arr[nr][nc] == Red) {
		int size = stacked[nr][nc].size();
		moveAtoB(stacked[r][c], stacked[nr][nc],chessInd,nr,nc);
		reverse(stacked[nr][nc].begin()+size , stacked[nr][nc].end());

	}
	//파랑색인 경우.  자신의 방향만 뒤고 반대로 이동.
	else if (arr[nr][nc] == Blue) {
		changeDir(chessInd);
		dir = vec[chessInd].dir;
		nr = r + dir_r[dir];
		nc = c + dir_c[dir];
		if (( nr <1 || nr > N || nc <1 || nc > N) || arr[nr][nc] == Blue)
			return false;

		if (arr[nr][nc] == White){
			moveAtoB(stacked[r][c], stacked[nr][nc], chessInd, nr, nc);
		}
		else if (arr[nr][nc] == Red) {
			int size = stacked[nr][nc].size();
			moveAtoB(stacked[r][c], stacked[nr][nc], chessInd, nr, nc);
			reverse(stacked[nr][nc].begin() + size, stacked[nr][nc].end());

		}
	}

	if (stacked[nr][nc].size() == 4 || stacked[r][c].size() == 4) {
		return true;
	}

	return false;
}

int moveFunc() {
	int turn = 1;
	while (turn <= 1000) {
		for (int i = 0; i < K; i++) {
			//체스말이 규칙에 따라 이동한다.
			if (moveChess(i)) {
				return turn;
			}
		}
		turn++;
	}
	return -1;
}


int main() {
	ios_base::sync_with_stdio(false);
	freopen("input.txt", "r", stdin);
	
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr[i+1][j+1];
		}
	}

	for (int i = 0; i < K; i++) {
		int r, c, dir;
		cin >> r >> c >> dir;
		vec.push_back(chess{ r,c,dir });

		stacked[r][c].push_back(i);
	}

	cout << moveFunc() << "\n";

	return 0;
}

 

질문글 보고 알았다.

턴이 진행되던 중에 말이 4개 쌓이는 순간 게임이 종료된다. ->> 이말은 4개 이상인듯...!!!@#!@#@!#

'알고리즘 문제 풀기' 카테고리의 다른 글

백준 2504: 괄호의 값, 1722번 순열의 순서, 13251번 조약돌 꺼내기.  (0) 2020.02.07
백준 1517번 : 버블 소트,12015번 가장 긴 증가하는 부분수열2  (0) 2020.02.01
프로그래머스 - 가장 먼 노드, 정수 삼각형  (0) 2020.01.23
백준 9934번: 완전 이진 트리 / 프로그래머스(카카오) : 길 찾기 게임 / 백준 12909번: 그래프 만들기.  (0) 2020.01.21
프로그래머스 - 탐욕법 : 체육복, 조이스틱  (0) 2020.01.20

'알고리즘 문제 풀기'의 다른글

  • 현재글백준 : 4358번 생태학 ,17837번 새로운 게임2

관련글

댓글

티스토리툴바