[14620 번] 꽃길

www.acmicpc.net/problem/14620

14620번: 꽃길

이 문제는 가능한 씨앗의 배치를 모두 검색한 뒤, 씨앗을 중심으로 4방향이 화단에 들어오면서, 겹치지 않는 경우에 따라 세 개의 꽃을 배치하고 해당 위치의 가격을 모두 더한 값 중 최소값을 찾는 문제입니다.

 

이 문제를 나눠보면 첫 번째로 씨앗을 배치하는 것, 두 번째로 씨앗이 꽃이 피었을 때 겹치지 않는지 판단하는 것, 겹치지 않는 경우에서 화단의 최소값을 찾는 것으로 나눌 수 있습니다.

 

가장 먼저 씨앗을 배치하는 것부터 살펴보자면 씨앗을 백트래킹을 통해서 경우를 파악할 수 있습니다.

(강의 : N-QUEEN문제 참고) 여기서 조금 더 세부적으로 보자면 꽃이 4방향으로 피어야 되기 때문에 화단의 끝 부분에는 씨앗을 심을 수 없다는 것입니다. (이것은 씨앗은 화단의 안쪽만을 사용할 수 있다는 것입니다.)

그림으로 살펴보면 초록색으로 색을 칠한 위치에는 씨앗을 심을 수 없다는 것입니다.

 

백트래킹

void dfs(int a, int cnt) {
	if (cnt == 3) { //선택지 3개가 완료되면 check
		check(); //check : 꽃이 피었을 때 겹치지 않는지 판단하고 최소값을 ans 저장
		return;
	}
	for (int i = a; i < N - 1; i++) { //백트래킹
		for (int j = 1; j < N - 1; j++) {
			if (!visit[i][j]) {
				visit[i][j] = true;
				dfs(i, cnt + 1);
				visit[i][j] = false;
			}
		}
	}
}

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

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

	for (int i = 1; i < N - 1; i++) { //i가 1부터 j가 1부터 시작하는 이유는 그림으로 설명함.
		for (int j = 1; j < N - 1; j++) { //백트래킹 시작
			visit[i][j] = true; //visit 배열 : 방문을 했는지 안했는지 판단
			dfs(i, 1);
			visit[i][j] = false; //visit 초기화
		}
	}
	cout << ans;
}

 

그 다음으로 꽃이 4방향으로 피었을 때 겹치지 않는지 판단한 뒤 겹치지 않았다면 화단의 최소 비용을 ans에 저장

 

씨앗 3개를 심고 check

int ans = 9876543;
int N;

int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };

void check() {
	bool temp[11][11] = { false, };
	
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (visit[i][j]) {
				temp[i][j] = true; cnt++;
				for (int k = 0; k < 4; k++) { //동 서 남 북 탐색
					int x = dx[k] + i;
					int y = dy[k] + j;
					if (!temp[x][y]) {
						temp[x][y] = true; cnt++;
					}
				}
			}
		}
	}
	if (cnt == 15) { //꽃잎의 총 면적이 15가 되야함.
		int term = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (temp[i][j])
					term += map[i][j];
			}
		}
		ans = min(ans, term);
	}
}

 

전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <cstring>

using namespace std;

typedef long long ll;

int map[11][11] = { 0, };
bool visit[11][11] = { false, };
int ans = 9876543;
int N;

int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };

void check() {
	bool temp[11][11] = { false, };
	
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (visit[i][j]) {
				temp[i][j] = true; cnt++;
				for (int k = 0; k < 4; k++) { //동 서 남 북 탐색
					int x = dx[k] + i;
					int y = dy[k] + j;
					if (!temp[x][y]) {
						temp[x][y] = true; cnt++;
					}
				}
			}
		}
	}
	if (cnt == 15) { //꽃잎의 총 면적이 15가 되야함.
		int term = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (temp[i][j])
					term += map[i][j];
			}
		}
		ans = min(ans, term);
	}
}

void dfs(int a, int cnt) {
	if (cnt == 3) { //선택지 3개가 완료되면 check
		check();
		return;
	}
	for (int i = a; i < N - 1; i++) { //백트래킹
		for (int j = 1; j < N - 1; j++) {
			if (!visit[i][j]) {
				visit[i][j] = true;
				dfs(i, cnt + 1);
				visit[i][j] = false;
			}
		}
	}
}

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

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

	for (int i = 1; i < N - 1; i++) {
		for (int j = 1; j < N - 1; j++) { //백트래킹 시작
			visit[i][j] = true;
			dfs(i, 1);
			visit[i][j] = false;
		}
	}
	cout << ans;
}