소풍

#include <iostream>
#include <cstring>
#define MAX 10
using namespace std;

int n, m; 
bool areFriends[MAX][MAX] = {false };
bool visited[MAX];

int countingPairs() {
	
	int targetStudent = -1; 

	// 짝을 찾아줄 아이를 탐색
	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			targetStudent = i;
			break;
		}
	}

	// 기저사례 : 모든 아이들이 짝을 찾았으면 종료
	if (targetStudent == -1)
		return 1;

	int ret = 0; 
	for (int i = targetStudent + 1; i < n; i++) {
		if (!visited[i] && areFriends[targetStudent][i]) {
			visited[targetStudent] = visited[i] = true;
			ret += countingPairs();
			visited[targetStudent] = visited[i] = false;
		}
	}
	return ret;
}

int main() {
	int cases; cin >> cases;
	while (cases--) {
		cin >> n >> m;
		for (int i = 0; i < m; i++) {
			int stu1, stu2;
			cin >> stu1 >> stu2;
			areFriends[stu1][stu2] = areFriends[stu2][stu1] = true;
		}

		cout << countingPairs() << endl; 
		for (int i = 0; i < 10; i++) {
			memset(areFriends[i], false, sizeof(bool) * 10);
		}
	}
}

(1) 숫자를 기준으로 매칭이 되어있는 경우에는 이차원 bool 자료형 배열을 만들어서 정보를 저장

(2) 여러번 테스트케이스를 만들어서 실행하는 경우, 전역으로 정의한 변수 혹은 배열을 다시 초기화화는 과정을 필수로 넣어야한다.

(3) 완전탐색에서는 중복이 되면 안되는 경우에서, 즉 (A, B)와 (B, A)가 같은 경우 위와 같이 target을 지정하고 그 다음부터 순차적으로 돌면서 문제를 해결한다.

게임판 덮기

• 오답 노트1
• 오답 노트2
• 종만북 개쩌는 포인트 ..
• 실수한 포인트

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#define MAX 20
using namespace std;

int h, w;
// vector<vector<int>> board;

// 배치 가능한 블럭 타입들
int blockType[4][3][2] = {
	{{0, 0}, {1, 0}, {1, 1}},
	{{0, 0}, {1,0}, {1, -1} },
	{{0, 0}, {0, 1}, {1, 1 }},
	{{0, 0}, {0, 1}, {1, 0}}
};

// Block을 끼워넣거나 (delta = 1)  다시 빼는 (delta = -1) 함수
bool setBlock(int board[MAX][MAX], int y, int x, int type, int delta) {
	bool flag = true; 

	for (int i = 0; i < 3; i++) {
		int ny = y + blockType[type][i][0];
		int nx = x + blockType[type][i][1];

		// 기저사례 1 게임판 안에 속해있지 않은 경우
		if (ny < 0 || ny >= h || nx < 0 || nx >= w)
			flag = false;
		else if ((board[ny][nx] += delta) > 1) {// 기저사례 2 비어있는 칸이 아닌 경우
			flag = false;
		}
		// cout << board[ny][nx] << endl;

	}
	return flag; 
}

int countBlock(int board[MAX][MAX]) {
	int x = -1, y = -1;
	for (int dy = 0; dy < h; dy++) {
		for (int dx = 0; dx < w; dx++) {
			if (!board[dy][dx]) { // 빈 칸이라면
				y = dy; x = dx;
				break;
			}
		}
		if (y != -1 || x != -1)
			break;
	}

	if (x == -1 || y == -1) // 모든 칸이 다 채워졌으면
		return 1;
	
	int ret = 0; 
	for (int type = 0; type < 4; type++) {
		if (setBlock(board, y, x, type, 1)) // 가능하면 삽입
			ret += countBlock(board); 
		setBlock(board, y, x, type, -1); // 해체
	}
	return ret; 
}

int main() {
	int cases; cin >> cases;
	while (cases--) {
		cin >> h >> w;
		int board[MAX][MAX];

		for (int dy = 0; dy < h; dy++) {
			for (int dx = 0; dx < w; dx++) {
				char input; cin >> input;
				switch (input) {
				case '#':
					board[dy][dx] = 1; 
					break;
				case '.':
					board[dy][dx] = 0; 
					break;
				}
			}
		}

		cout << countBlock(board) << endl;
	}
}

여기서 board를 전역으로 선언해서 풀었었는데, 이상하게 답이 이상하게 나왔다. 첫번째 시도부터 이상하게 나오는걸 보니 테스트케이스 원인은 아니었고, 초기화가 잘 안되서 함수로 넘어간건가 ? 싶었다.

아무튼 해결

시계 맞추기

알게된 점

(1) 최적화 문제는 INF를 쓰는게 핵심인가 보다 !!!!!!!!!!!!!!!

ret = 0에 재귀호출된 값을 더해주는 기존 문제와는 다르게 여기에서는 min을 사용하므로 처음 시드값을 INF로 설정해서 그 뒤의 값과 비교해 점차 줄여가는 방식으로 최솟값을 찾아간다.

그리고, 기저 사례에서 1을 리턴해서 ret에 반환값을 차례로 더하여 “가능한 총 횟수”를 찾았던 기존과는 다르게, 최적화 문제에서는 특정 조건을 만족한 경우 최적의 답을 찾기 위해서 INF를 사용해야하는 것이다.