[boj][c++] 14620 꽃길

ppparkta·2022년 11월 21일

Problem solving

목록 보기

48/65

14620 꽃길

접근방법

애매하게 BFS/DFS로 분류할 수 있을 것 같은 문제였다. 씨앗을 심을 지점을 구하는 것은 DFS로 구현할 수 있고 DFS내에서 세세하게 조건을 분류할 때 BFS(라기보단 브루트포스...?)스러운 방법을 사용했다.

사용한 알고리즘은 단순하지만 구현까지의 사고 과정이 복잡했다.

씨앗을 심을 수 있는 지점인지 확인하기
씨앗을 심었을 때 드는 비용 구하기
세개의 씨앗을 심었을 때 드는 가장 적은 비용 구하기

풀이

1. 씨앗을 심을 수 있는 지점인지 확인하기

씨앗을 심을 수 있는 지점은

0~n-1을 벗어나지 않는 x,y좌표
다른 꽃이 심어진 장소와 겹치지 않는 좌표

두가지를 확인하면 된다. 좌표를 벗어나지 않는 구간은 반복을 1~n-2 이내로 돌려서 간단히 해결했다. 다른 꽃과 겹치지 않는 좌표는 bool 자료형으로 방문표시를 하여 해결했다.

방문 표시를 위해 dx,dy배열을 만들어서 연산에 활용했다.

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

bool use_check(int y, int x)
{
	if (visited[y][x])
		return false;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (visited[ny][nx])
			return false;
	}
	return true;
}

2. 씨앗을 심었을 때 드는 비용 구하기

씨앗을 심었을 때 드는 비용은 씨앗을 심을 수 있는 지점인지 확인할 때와 비슷하게 dx, dy배열을 이용해서 계산했다.

int flower_sum(int y, int x) {
	int sum = arr[y][x];
	visited[y][x] = true;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		sum += arr[ny][nx];
		visited[ny][nx] = true;
	}
	return sum;
}

3. 세개의 씨앗을 심었을 때 드는 가장 적은 비용 구하기

위의 두가지 로직을 구현했다면, DFS함수 내에 잘 합쳐주면 된다.

앞서 말했듯 좌표를 벗어나지 않는 구간은 반복은 1~n-2 이내로 돌려서 해결했다. 이것을 유의해서 DFS함수를 만들면 된다.

주의해야 하는 것은 flower_sum함수에서 bool형 배열을 true로 수정했기 때문에 재귀가 끝났을 때 이를 다시 원상복구 해야한다.

또한 씨앗은 세개만 심을 것이므로 매개변수로 씨앗의 개수를 의미하는 자료를 줘야한다.

void dfs(int depth, int sum) {
	if (depth == 3) {
		ans = min(ans, sum);
		return;
	}
	for (int i = 1; i < n - 1; i++) {
		for (int j = 1; j < n - 1; j++) {
			if (use_check(i,j)) {
				tmp = flower_sum(i, j);
				dfs(depth + 1, sum + tmp);
				first_state(i, j);
			}
		}
	}
}

전체 소스코드

#include <iostream>
#include <algorithm>
using namespace std;

int n, tmp, ans = 10000;
int arr[11][11];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
bool visited[11][11];

void first_state(int y,int x) {
	visited[y][x] = false;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		visited[ny][nx] = false;
	}
	return;
}

int flower_sum(int y, int x) {
	int sum = arr[y][x];
	visited[y][x] = true;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		sum += arr[ny][nx];
		visited[ny][nx] = true;
	}
	return sum;
}

bool use_check(int y, int x)
{
	if (visited[y][x])
		return false;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (visited[ny][nx])
			return false;
	}
	return true;
}

void dfs(int depth, int sum) {
	if (depth == 3) {
		ans = min(ans, sum);
		return;
	}
	for (int i = 1; i < n - 1; i++) {
		for (int j = 1; j < n - 1; j++) {
			if (use_check(i,j)) {
				tmp = flower_sum(i, j);
				dfs(depth + 1, sum + tmp);
				first_state(i, j);
			}
		}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}
	dfs(0, 0);
	cout << ans;
}