대엉코딩

www.acmicpc.net/problem/17825

1. 풀이방법

- 쉽다고 생각하면서 , 시작해서 개고생하며 어렵게 끝낸 문제입니다.....

- 첫번째 문제점, 30 노드가 중복되는 것을 체크하지 못한점.

- 30 노드에 도착하면 방향을 바꾸도록 설정했다가 다른 30 (끝 쪽에 가까운) 거기에 말들이 도착헀을때도 방향을 바꾸는 현상 발생.

- 두번째 문제점, 방문체크를 할때 여러개 있는 노드들을 고려하지 않은 것.

- 문제를 보면, 두개이상 존재하는 노드들이 있다 (16, 22,28,30.....)

- 결국 현재 말들의 위치만을 비교함으로써 겹쳐지는지 아닌지 알 수 가 없다.

- 결국 코드를 싹 지우고, 다시 짜면서 해결한 방법은

- 각각 고유의 번호를 가지는 노드들로 같은 모양의 그래프를 만들어 준 후, 문제에서의 노드들은 점수들로서

- 매칭을 시켜주었습니다. 그러면 첫, 두 번째 문제점들이 모두 해결됩니다.

- 그림을 보시면 아이디어를 이해하시기 편할 겁니다.

- 전체적인 문제해결은 dfs를 이용한 완전탐색 입니다.

2. 주의사항

- 일단 코드를 작성하기 전, 문제를 항상 정확히 파악하고 시작하고자 노력하지만

- 이 문제처럼, 처음 시작할 때 발생하는 문제를 예상하지 못하고 시작하면 굉장히 어려워 지고 꼬입니다....

- 역시, 주의사항은...... 문제를 꼼꼼히 잘 분석하자......

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

// 시작노드 0, 도착점 노드 21
int route[4][33];
int score[33]; // 점수계산을 위한 노드
int maxresult;
int inputnum[10];
pair<int, int> ob[4]; //4개의말 (현재위치, 타고있는 방향)

void inputs() {
	for (int i = 0; i < 10; i++) {
		cin >> inputnum[i];
	}
}
void setscore() {
	for (int i = 1; i <= 20; i++) {
		score[i] = 2 * i;
	}
	score[22] = 13; score[23] = 16; score[24] = 19;
	score[25] = 25; score[30] = 26; score[29] = 27;
	score[28] = 28; score[26] = 22; score[27] = 24;
	score[31] = 30; score[32] = 35; score[21] = 0;
}
void makegraph() {
	for (int i = 0; i < 21; i++) {
		route[0][i] = i + 1;
	}
	route[0][21] = 21;
	route[1][5] = 22; route[1][22] = 23; route[1][23] = 24;
	route[1][24] = 25; route[1][25] = 31; route[1][31] = 32;
	route[1][32] = 20; route[1][20] = 21; route[1][21] = 21;
	route[2][10] = 26; route[2][26] = 27; route[2][27] = 25;
	route[2][25] = 31; route[2][31] = 32; route[2][32] = 20;
	route[2][20] = 21; route[2][21] = 21;
	route[3][15] = 28; route[3][28] = 29; route[3][29] = 30;
	route[3][30] = 25; route[3][25] = 31; route[3][31] = 32;
	route[3][32] = 20; route[3][20] = 21; route[3][21] = 21;
}
bool existcheck(int s,int index) {
	if (s == 21) return false;
	for (int i = 0; i < 4; i++) {
		if (i == index) continue;
		if (ob[i].first == 21) continue;
		if (ob[i].first == s) return true;
	}
	return false;
}
void makecase(int cnt,int resultsum) {
	if (cnt == 10) {
		maxresult = max(resultsum, maxresult);
		return;
	}
	int thisnum = inputnum[cnt];
	for (int i = 0; i < 4; i++) {
		if (ob[i].first == 21) continue; //이미 도착점에 있는 말
		int prevnum = ob[i].first;
		int prevdir = ob[i].second;
		for (int j = 0; j < thisnum; j++) {
			ob[i].first = route[prevdir][ob[i].first];
		}
		if (ob[i].first == 5) ob[i].second = 1;
		if (ob[i].first == 10) ob[i].second = 2;
		if (ob[i].first == 15) ob[i].second = 3;

		if (!existcheck(ob[i].first,i)) {
			makecase(cnt + 1, resultsum + score[ob[i].first]);
		}
		ob[i].first = prevnum;
		ob[i].second = prevdir;

	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	setscore();
	makegraph();
	makecase(0,0);
	cout << maxresult;
	return 0;
}

www.acmicpc.net/problem/17136

1. 풀이방법

- 하... 이문제 때문에 여간 고생한게 아니다;;

- 정확한 이유는 모르겠는데 처음에 맵을 탐색하다가 1을 발견하면 5가지의 색종이를 모두 붙이는 식으로

- 구현을 했었는데 계속 종료조건이 애매해서 어쩔 줄 몰라 하다가,,,, 탐색을 하는 부분이랑 색종이를 붙여보는

- 것을 나눠서 구현했더니 해결이 되었습니다.

- 자신감이 딱 붙어갈 타이밍에 좌절을 준 문제였습니다.....나중에 다시 풀어도 고생할 듯한....

- 전체적인 구조를 종료조건을 잘 생각해서 짜야할 것 같습니다.... 아이디어는 금방 떠올렸으나..참;;

- 개인적으로 힘든 문제였습니다..

2.주의사항

- 종료조건을 적절히 사용할 수 있게끔 전체적인 구조를 생각하고 짜자.....!

3.나의 코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int map[10][10];
int colorpaperset[6];
int minimumpapaer = 101;
void doattach(int, int, int);

void inputsetting() {
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 1; i < 6; i++) {
		colorpaperset[i] = 5;
	}
}
bool canattach(int x, int y, int r) {
	if (x + r > 10 || y + r > 10) { return false; }
	for (int i = x; i < x+r; i++) {
		for (int j = y; j < y+r; j++) {
			if (map[i][j] == 0) return false;
		}
	}
	return true;
}
void setmap(int x, int y, int r) {
	for (int i = x; i < x + r; i++) {
		for (int j = y; j < y + r; j++) {
			map[i][j] =0;
		}
	}
}
void unsetmap(int x, int y, int r) {
	for (int i = x; i < x + r; i++) {
		for (int j = y; j < y + r; j++) {
			map[i][j] = 1;
		}
	}
}

void attach(int x, int y, int r) {
	int tmpx, tmpy;
	bool c = false;
	for (int i = x; i < 10; i++) { //1인 부분을 탐색
		for (int j = 0; j < 10; j++) {
			if (map[i][j] == 0) {
				if (i == 9 && j == 9) { minimumpapaer = min(minimumpapaer, r); return; }
				// 재귀를 통해 여기까지 왔다는 것 자체가 이미 1을 다 0으로 바꾸고 도착했다는 것
				continue;}
			tmpx = i; tmpy = j; c = true; break;
		}
		if (c == true) break;
	}
	doattach(tmpx, tmpy, r);
}
void doattach(int x, int y, int r) {//붙이기를 시도한다.
	for (int k = 5; k > 0; k--) {
		if (canattach(x, y, k) == true && colorpaperset[k] > 0) {
			setmap(x, y, k);
			colorpaperset[k]--;
			attach(x, y, r + 1); //재귀를 통해 다시 탐색을 수행
			colorpaperset[k]++; //다른 종이에 대해서도 수행을 해봐야하므로
			unsetmap(x, y, k); //원상 복구
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	inputsetting();
	attach(0, 0, 0);
	if (minimumpapaer == 101) { cout << -1; }
	else { cout << minimumpapaer; }
	return 0;
}

https://www.acmicpc.net/problem/14889

- dfs 를 이용한 완전 탐색 문제였습니다. (백트래킹 이라고도 하는...)

- 사실 저는 백트래킹이라는 개념을 딱히 그렇게 정의지어 배워본 적이 없어서 다른 문제하나를 풀다가

- 접한적은 있습니다만....

- 이문제는 dfs 느낌과 비슷하게 재귀를 이용 하여 모든 경우의 수를 모두 탐색 하는 방향으로 해결하였습니다.

- 다른건 어려운 것이 없고 최대20 명이 되는 n을 두팀에 나누어 넣는 모든 경우의 수를 어떻게 구현해 내는지가

- 핵심이였던 문제인 것 같습니다..

<코드>

https://www.acmicpc.net/problem/6603

dfs라고 보면 dfs인 것 같기도 한데

많은 분들이 dfs와 백트래킹 이라고 많이 하시던데 그렇게들 푸시고

아직 이에대한 개념이 충분치 않아서....... 좀 오래걸리기도 했고 사실 아직도 잘 모르겠습니다...

다른분들의 코드도 보고 참고 하였습니다. 

일단은 이해를 하는 것을 우선으로 두기로 하였습니다........... 공부 해야겠네요....

저처럼 이해가 안되실 분 들을 위해 가능한 쉽게 제가 이해한 방식을 올리겠습니다.

<필기>

<코드>