대엉코딩

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/2583

- 기본적인 dfs 문제입니다. 

- 문제를 읽으면 dfs구나 알 수 있고 처음 접해서 풀기 좋은 문제인 것 같습니다.

- 좌표 기준 때문에 i,j만 조금 신경써서 해주시면 됩니다(문제에 맞추어서)

- 전 항상 몇번 풀어도 좌표 기준 신경 쓰는게 그렇게 짜증나더라는...ㅎ;;;

<필기>

<코드>

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

DFS와 BFS를 탐색을 하는 기본문제입니다.

개념을 익히는 정도 라고 하면 되겠네요!

깊이우선 탐색을 먼저 하고 너비우선 탐색을 하면 됩니다.

이차원 배열을 통해서 점과 점이 연결되었는지 여부를 확인(간선)

간선은 입력받을떄 [x][y] =1은 물론 [y][x]=1도 넣어주었습니다(양방향 간선 이므로)

일차원 배열을 통해 방문을 했는지 여부를 확인하는 용도로 사용하였습니다.

<main> 함수

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

DFS 기본 문제 느낌이였습니다.

깊이우선 탐색입니다.

한 점(집) 을 발견하면 일단 그 집과 연결된 모든 집을 탐색하고(탐색하면서 방문 했다고 체크)

다음에 FOR문을 돌때는 집이 있어도 이미 방문되었다고 표시가 되어 있으면

DFS를 돌지 않도록 하였습니다.

MAP은 그냥 정적으로 만들었고 (N)값 범위가 정해져 있으므로 N의 최대값으로 설정 하였습니다.

체크나 출력은 N값을 이용하면 되므로..