BOJ 14620. 꽃길

🙇‍♀️[Silver II] 꽃길 - 14620

문제 링크

성능 요약

메모리: 2028 KB, 시간: 36 ms

분류

백트래킹, 브루트포스 알고리즘

제출 일자

2024년 11월 21일 15:44:20

문제 설명

2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다.

진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므로 진아는 다음해 식목일 부터 꽃길을 걸을 수 있다.

하지만 진아에게는 꽃의 씨앗이 세개밖에 없었으므로 세 개의 꽃이 하나도 죽지 않고 1년후에 꽃잎이 만개하길 원한다.

꽃밭은 N*N의 격자 모양이고 진아는 씨앗을 (1,1)~(N,N)의 지점 중 한곳에 심을 수 있다. 꽃의 씨앗은 그림 (a)처럼 심어지며 1년 후 꽃이 피면 그림 (b)모양이 된다.

꽃을 심을 때는 주의할 점이있다. 어떤 씨앗이 꽃이 핀 뒤 다른 꽃잎(혹은 꽃술)과 닿게 될 경우 두 꽃 모두 죽어버린다. 또 화단 밖으로 꽃잎이 나가게 된다면 그 꽃은 죽어버리고 만다.

그림(c)는 세 꽃이 정상적으로 핀 모양이고 그림(d)는 두 꽃이 죽어버린 모양이다.

하이테크 앞 화단의 대여 가격은 격자의 한 점마다 다르기 때문에 진아는 서로 다른 세 씨앗을 모두 꽃이 피게하면서 가장 싼 가격에 화단을 대여하고 싶다.

단 화단을 대여할 때는 꽃잎이 핀 모양을 기준으로 대여를 해야하므로 꽃 하나당 5평의 땅을 대여해야만 한다.

돈이 많지 않은 진아를 위하여 진아가 꽃을 심기 위해 필요한 최소비용을 구해주자!

입력

입력의 첫째 줄에 화단의 한 변의 길이 N(6≤N≤10)이 들어온다.

이후 N개의 줄에 N개씩 화단의 지점당 가격(0≤G≤200)이 주어진다.

출력

꽃을 심기 위한 최소 비용을 출력한다.

🚀풀이

3개의 좌표를 선택하고 꽃잎이 곂치는지 확인한다.
곂치지 않는다면 각 비용을 계산한다.
모든 경우의 수를 탐색하고 최소의 비용을 구한다.

먼저 3개의 좌표를 구하기 위해서 2차원 배열을 1차원 배열로 생각했다.
nn배열이므로 좌표를 nn만큼 순회하면 된다.
그리고 3개의 좌표를 선택해야하므로 3중 for문을 사용했다.

// 3개 선택
for (int i = 0; i < n * n - 2; ++i)
{
	for (int j = i + 1; j < n * n - 1; ++j)
	{
		for (int k = j + 1; k < n * n; ++k)
		{
			// 1차원 인덱스를 2차원 좌표로 변환
			int row1 = i / n;
			int col1 = i % n;
			int row2 = j / n;
			int col2 = j % n;
			int row3 = k / n;
			int col3 = k % n;
		}
	}
}

이렇게 하면 3개의 좌표를 가져올 수 있다.

그리고 꽃이 가장 자리에 있을 경우는 꽃잎이 범위를 벗어나므로 이 경우를 생각해줬다.

if (row1 == 0 || col1 == 0 || row1 == n - 1 || col1 == n - 1)
	continue;
if (row2 == 0 || col2 == 0 || row2 == n - 1 || col2 == n - 1)
	continue;
if (row3 == 0 || col3 == 0 || row3 == n - 1 || col3 == n - 1)
	continue;

꽃잎이 곂치는 경우를 생각하기 위해서 check배열을 따로 만들어서 사용할 수도 있지만 set을 이용해서 중복을 체크했다.
동시에 temp에 비용을 계산도 해줬다.

// 조합 저장
set<pair<int, int>> s;
int temp = 0;
s.insert({ row1, col1 }); temp += board[row1][col1];
s.insert({ row2, col2 }); temp += board[row2][col2];
s.insert({ row3, col3 }); temp += board[row3][col3];
for (int dir = 0; dir < 4; ++dir)
{
	pair<int, int> n1 = { row1 + dy[dir], col1 + dx[dir] };
	pair<int, int> n2 = { row2 + dy[dir], col2 + dx[dir] };
	pair<int, int> n3 = { row3 + dy[dir], col3 + dx[dir] };
	s.insert(n1);
	s.insert(n2);
	s.insert(n3);
	temp += board[n1.first][n1.second];
	temp += board[n2.first][n2.second];
	temp += board[n3.first][n3.second];
}
// 꽃잎이 곂치는가?
if (s.size() != 15)
	continue;

set의 개수가 15개가 아니라면 중복된 경우가 생기는 경우이므로 넘어간다.
최종적으로 최소의 비용을 확인하고 결과를 구한다.
res = min(res, temp);

3개의 좌표라고 명시된 문제여서 3중 for문도 나쁘지 않다고 생각하지만 만약에 꽃의 개수까지 문제에서 달라질 수 있는 경우라면 for문이 아니라 순열을 직접 구해야 할 필요가 생긴다.

순열을 만들어본 경험이 있어서 그걸 다시 복습해보자면 아래와 같이 짰다.

int n, r, ch[20];
void DFS(int s, int L)
{
	if (L == r)
	{
		for (int i = 0; i < L; ++i)
		{
			cout << ch[i] << " ";
		}
		cout << endl;
	}
	else
	{
		for (int i = s; i < n; ++i)
		{
			ch[L] = i;
			DFS(i + 1, L + 1);
		}
	}
}

2차원 배열에서 3개를 선택해야하는데 pair<int, int>를 담는 vector를 다시 만들어서 하나의 인덱스로 좌표를 가져오는 방식을 만들면 저 방법을 통해서 문제를 해결할 수도 있을거같다.

🚀코드

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

int n, res = INT_MAX;
vector<vector<int>> board;
pair<int, int> coordi;
int dy[] = { 0, 1, 0, -1 };
int dx[] = { 1, 0, -1, 0 };

void solve()
{
	cin >> n;
	board = vector<vector<int>>(n, vector<int>(n));
	for (int y = 0; y < n; ++y)
	{
		for (int x = 0; x < n; ++x)
		{
			cin >> board[y][x];
		}
	}

	// 3개 선택
	for (int i = 0; i < n * n - 2; ++i)
	{
		for (int j = i + 1; j < n * n - 1; ++j)
		{
			for (int k = j + 1; k < n * n; ++k)
			{
				// 1차원 인덱스를 2차원 좌표로 변환
				int row1 = i / n;
				int col1 = i % n;
				int row2 = j / n;
				int col2 = j % n;
				int row3 = k / n;
				int col3 = k % n;
				if (row1 == 0 || col1 == 0 || row1 == n - 1 || col1 == n - 1)
					continue;
				if (row2 == 0 || col2 == 0 || row2 == n - 1 || col2 == n - 1)
					continue;
				if (row3 == 0 || col3 == 0 || row3 == n - 1 || col3 == n - 1)
					continue;

				// 조합 저장
				set<pair<int, int>> s;
				int temp = 0;
				s.insert({ row1, col1 }); temp += board[row1][col1];
				s.insert({ row2, col2 }); temp += board[row2][col2];
				s.insert({ row3, col3 }); temp += board[row3][col3];
				for (int dir = 0; dir < 4; ++dir)
				{
					pair<int, int> n1 = { row1 + dy[dir], col1 + dx[dir] };
					pair<int, int> n2 = { row2 + dy[dir], col2 + dx[dir] };
					pair<int, int> n3 = { row3 + dy[dir], col3 + dx[dir] };
					s.insert(n1);
					s.insert(n2);
					s.insert(n3);
					temp += board[n1.first][n1.second];
					temp += board[n2.first][n2.second];
					temp += board[n3.first][n3.second];
				}
				// 꽃잎이 곂치는가?
				if (s.size() != 15)
					continue;

				// 비용 체크
				res = min(res, temp);
			}
		}
	}

	cout << res;
}

int main()
{
	FILE* stream;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen_s(&stream, "input.txt", "rt", stdin);

	solve();

	return 0;
}