백준_14620_꽃길

으아아아아아ㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏ

왜 틀린지 모르겠음 질문글들도 없음,,,,,,,, 쉬운 문제 같은데ㅔㅔㅔㅔㅔㅔㅔㅔ

완전탐색 Backtracking으로 풀었음

일단 틀린코드라도 허허,, 나중에 수정해야지 

#include<iostream>
#include<vector>

using namespace std;

vector<vector<int>> arr;
vector<vector<int>> visited_map;

int n; // 사이즈

	   // 좌표이동 - 상, 하, 좌, 우, 현
int ax[5] = { 0, 0, -1, +1, 0 };
int ay[5] = { +1, -1, 0, 0, 0 };

bool visited_all(int _y, int _x) {

	if ((_x<1 || _x>n - 2) ||
		(_y<1 || _y>n - 2))
	{
		return false;
	}

	if (visited_map[_y][_x] == 1) {
		return false;
	}
	if (_y - 1>0 && visited_map[_y - 1][_x] == 1) {
		return false;
	}
	if (_y + 1<n && visited_map[_y + 1][_x] == 1) {
		return false;
	}
	if (_x - 1>0 && visited_map[_y][_x - 1] == 1) {
		return false;
	}
	if (_x + 1<n && visited_map[_y][_x + 1] == 1) {
		return false;
	}
	return true;
}

pair<int, int> makeNextPosition(int _y, int _x) {
	pair<int, int> p; // y,x

					  // 오른쪽으로 이동하는데 배열의 idx를 넘어선다면
	if (_x + 2>n - 2) { // 아래 줄의 가장 왼쪽
		p.first = _y + 1;
		p.second = 1;
	}
	else { // 오른쪽으로 이동
		p.first = _y;
		p.second = _x + 2;
	}

	return p;
}

int func(int _y, int _x, int min_sum, int sum, int cnt_flowers) {

	// 탈출 조건
	// 꽃을 다 심은 경우
	if (cnt_flowers == 3) {
		if (min_sum > sum) {
			// min_sum을 업데이트
			min_sum = sum;
		}
		return min_sum;
	}

	// 탈출 조건
	// 꽃을 다 심지 않았는데,
	// 이미 sum> min_sum 이면 더 이상 계산할 필요가 없음
	if (min_sum< sum) {
		return min_sum;
	}

	// 탈출조건
	// _x,_y가 배열 arr의 index를 넘어가면 
	// return min_sum
	if ((_x<1 || _x>n - 2) ||
		(_y<1 || _y>n - 2))
	{
		return min_sum;
	}

	for (int i = _y; i < n; i++) {
		for (int j = _x; j < n; j++) {
			// 모두 방문한 적 없어서 (겹치지않음) 방문이 가능함.
			if (visited_all(i, j) == true) {
				for (int k = 0; k < 5; k++) {
					sum += arr[i + ay[k]][j + ax[k]];
					visited_map[i + ay[k]][j + ax[k]] = 1;
				}
				cnt_flowers++;
				// 다음 확인 위치 생성하는 함수
				pair<int, int> p = makeNextPosition(i, j);
				int temp_sum = func(p.first, p.second, min_sum, sum, cnt_flowers);
				if (temp_sum < min_sum) {
					min_sum = temp_sum;
				}
				// 재귀함수 호출 후에 끝나서 돌아오면 다시 for문 반복. (더 작은 값이 가능할 수 있기때문에)
				// 방문한 곳 초기화해주기
				for (int k = 0; k < 5; k++) {
					sum -= arr[i + ay[k]][j + ax[k]];
					visited_map[i + ay[k]][j + ax[k]] = 0;
				}
				cnt_flowers--;
			}
		}
	}
	return min_sum;
}

int main() {

	cin >> n;

	arr.assign(n, vector<int>(n, 0)); // arr[n][n], 초기화 0
	visited_map.assign(n, vector<int>(n, 0));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}

	int res = func(1, 1, INT_MAX, 0, 0);
	cout << res << endl;
	return 0;
}