[백준/C++] 꽃길_14620

📝 문제

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

💻 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <typeinfo>
#include <string>
#include <queue>
#include <vector>

using namespace std;

int n;
int MAP[201][201];
int used[201][201];
int MIN = 213456789;

void dfs(int total, int cnt) {
	if (total > MIN) return;

	if (cnt == 3) {
		MIN = min(MIN, total);
		return;
	}

	int dr[] = { 0,0, 0, 1, -1 };
	int dc[] = { 0,1, -1, 0, 0 };

	for (int i = 2; i <= n - 1; i++) {
		for (int j = 2; j <= n - 1; j++) {
			int total2 = 0;
			bool flag = false;
			for (int k = 0; k < 5; k++) {
				int nextRow = i + dr[k];
				int nextCol = j + dc[k];
				if (used[nextRow][nextCol] == 1) {
					flag = true;
					break;
				}
			}

			if (flag) continue;

			for (int k = 0; k < 5; k++) {
				int nextRow = i + dr[k];
				int nextCol = j + dc[k];
				used[nextRow][nextCol] = 1;
				total2 += MAP[nextRow][nextCol];
			}

			dfs(total + total2, cnt + 1);

			for (int k = 0; k < 5; k++) {
				int nextRow = i + dr[k];
				int nextCol = j + dc[k];
				used[nextRow][nextCol] = 0;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	// 세 씨앗이 모두 꽃 피고 가장 싼 가격
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> MAP[i][j];
		}
	}

	// (1,1) ~ (n,n) => (2,2) ~ (n-1, n-1)

	dfs(0, 0);
	cout << MIN;
	
	return 0;
}

💡 Point

계속 94~95퍼에서 시간초과가 발생했다. 다른 코드를 봐도 원리는 똑같아서 왜 틀렸는지 찾기 어려웠다. 노가다로 한줄씩 바꿔보다가 꽃을 다 심었을 때 최솟값 갱신을 if문이 아닌 min 함수를 쓰니깐 맨 처음코드로 통과됐다. 이유를 찾고 싶었는데 잘 안나와서 일단 크기 비교는 min, max로 외우기로 했다!