[C++] 백준(BOJ) - 15686 : 치킨 배달

18 Oct 2023 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 알고리즘
• 풀이
• 코드
• 평가

문제

백준(BOJ) - 15686 : 치킨 배달(링크)

알고리즘

1. 브루트포스
2. 완전탐색
3. 최대, 최소값
4. 조합

풀이

1. 브루트포스를 기반으로 시간복잡도 어림잡아 계산해보기
   • 문제의 전제조건확인 (집의 수 2N 넘지 않고, M은 13보다 작거나 같다)
   • 13Cx * 100 최대 시간복잡도
2. 좌표평면으로 위치가 주어지는 경우 pair<int, int> 형을 사용해서 index화 시킨다
3. 최대-최소값을 구하기 위해서는 미리 최대-최소값을 초기화 시켜준다

코드

// BOJ-15686 : 치킨배달
#include<bits/stdc++.h>
using namespace std;

int n, m, ans = 2147000000, a[54][54];

vector<pair<int, int>> _home, _chicken;
vector<vector<int>> _chickenList;

// 조합
void combi(int start, vector<int> v)
{
	if (v.size() == m)
	{
		_chickenList.push_back(v);
		return;
	}

	for (int i = start + 1; i < _chicken.size(); i++)
	{
		v.push_back(i);
		combi(i, v);
		v.pop_back();
	}
	return;
}

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

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> a[i][j];
			if (a[i][j] == 1) _home.push_back({ i,j });
			if (a[i][j] == 2) _chicken.push_back({ i,j });
		}
	}

	// 치킨 집 선별 (조합)
	vector<int> v;
	combi(-1, v);

	// 남은 치킨집 중
	for (vector<int> cList : _chickenList)
	{
		int res = 0;
		// 모든 집을 순회
		for (pair<int, int> home : _home)
		{
			int m_min = 2147000000;

			// 뽑은 치킨집과의 최소거리 완전탐색
			for (int ch : cList)
			{
				int _dist = abs(home.first - _chicken[ch].first) + abs(home.second - _chicken[ch].second);
				m_min = min(m_min, _dist);
			}
			res += m_min;
		}
		ans = min(ans, res);
	}

	cout << ans << '\n';

	return 0;
}

평가

• 최악의 시간복잡도를 어림잡아 계산하는 방법을 항상 연습해보기
• 단계적으로 로직을 설계 해 나가기