백준 15683 c++

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

using namespace std;

int N, M;
int ans;
int arr[9][9];
int dx[4] = { 1, 0, -1, 0 }; //90도 방향으로 수정
int dy[4] = { 0, 1, 0, -1 };
vector<pair<int, int>> v;

int count(void) {
	int cnt=0;
	for (int i = 0;i < N;i++) {
		for (int j = 0;j < M;j++) {
			if (arr[i][j] == 0) {
				cnt++;
			}
		}
	}
	return cnt;
}

void copy(int cpy0[9][9], int cpy[9][9]) {
	for (int i = 0;i < N;i++) {
		for (int j = 0;j < M;j++) {
			cpy0[i][j] = cpy[i][j];
		}
	}
}

void point(int x, int y, int num) {
	num = num % 4;
	while (1) {
		y = y + dy[num];
		x = x + dx[num];
		if (arr[y][x] == 6) return;
		if (y < 0 || x < 0) return;
		if (y >= N || x >= M) return;
		if (arr[y][x]!=0) continue;
		arr[y][x] = 9;
	}
	return;
}

void solve(int cnt) {
	int map[9][9];
	if (cnt == v.size()) {
		ans = min(count(), ans);
		return;
	}
	for (int i = 0;i < 4;i++) {
		copy(map, arr);
		int y = v[cnt].first;
		int x = v[cnt].second;
		int num = arr[y][x];
		if (num == 1) {
			point(x, y, i);
		}
		else if (num == 2) {
			point(x, y, i);
			point(x, y, i + 2);
		}
		else if (num == 3) {
			point(x, y, i);
			point(x, y, i + 1);
		}
		else if (num == 4) {
			point(x, y, i);
			point(x, y, i + 1);
			point(x, y, i + 2);
		}
		else if (num == 5) {
			point(x, y, i);
			point(x, y, i + 1);
			point(x, y, i + 2);
			point(x, y, i + 3);
		}
		solve(cnt + 1);
		copy(arr, map);
	}
}
int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> N >> M;
	for (int i = 0;i < N;i++) {
		for (int j = 0;j < M;j++) {
			cin >> arr[i][j];
			if (arr[i][j]>=1 && arr[i][j]<6) {
				v.push_back({ i, j });
			}
		}
	}
	ans = 999999;
	solve(0);
	cout << ans << endl;
	return 0;
}

시뮬레이션이라고 생각해서 모든 경우에 대해서 완전 탐색하는 방식으로 구현했다.

기존의 state를 어떻게 저장해야하는지에 대해서 고민했다. 배열을 두개 두어서 하나는 global로 두고 하나는 backup 용도로 local로 선언했다. local로 선언한 배열을 참조해서 copy 하는 방식으로 재귀문을 돌아왔을 때 참고할 수 있도록 구현했다.

 

문제를 풀면서 있던 에러 

1. dx, dy 배열을 처음에 {1,  -1, 0, 0} , {0, 0, 1, -1} 이런식으로 선언했다. 그러고 각각의 케이스에 대해서 point로 뒀는데 90도방향으로 이루어져있지 않기 때문에 i가 변할 때 값이 이상해질 수 있다는 것을 간과했다.

2. 두번째 에러도 dx, dy배열에서 cnt값을 통해서 참고했는데 %4를 포함하는 것을 놓쳤다.