BaekJoon 15686번: 치킨 배달(C++)

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

15686번: 치킨 배달

해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다.

 

풀이법

1) dfs를 활용하면 풀 수 있는 문제이다. (일종의 백트래킹)

2) bfs를 활용하여 접근 시에 시간 초과가 발생할 수 있다. |x1-x2|+|y1-y2|가 거리가 되므로 거리를 계산 시에 위 식을 활용하였다.

3) 1이 들어가 있는 x의 좌표와 y의 좌표를 ones 배열에 담아 주었으며, 2가 들어 있는 x의 좌표와 y의 좌표를 twos 배열에 담아주었다.

4) 이후 dfs를 활용 시에 index와 cnt를 인자로 두어 cnt가 문제에서 주어진 m과 같아질 경우 1에서 각 치킨집 까지의 거리의 합을 구했다.

5) dfs의 인자 중 index는 twos의 배열의 크기가 되었을 때 종료 시켰다. 겹치지 않게 m개의 인자를 뽑기 위해 재귀를 설정하는 것이 이 문제의 핵심이었다.

 

twos 배열에 5개의 값이 존재할 때(즉 배열에 2의 값이 5개 있을때) 존재할 수 있는 치킨 집의 최대 값이 2이면(m=2)

twos배열의 index를 기준으로 나타내면

(0,1) ,(0,2), (0,3), (0,4) / (1,2), (1,3), (1,4) / (2,3), (2,4) / (3,4)

와 같은 순서로 모든 경우의 수를 계산해 보고 1과의 거리 합이 최소가 되는 것을 구하면 된다.

	visited[index] = true;
	dfs(index + 1, cnt + 1);
	visited[index] = false;
	dfs(index + 1, cnt);

visited 값에 방문한 것을 담는다고 했을 때 해당 방식으로 재귀를 작성하면, 문제에서 요구한 순서대로 twos 배열에서 값을 index에 알맞게 뽑을 수 있었다.

 

#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <math.h>
#include <map>
#define INF 987654321
using namespace std;
int n, m;
int arr[51][51];
vector<pair<int, int>> ones;
vector<pair<int, int>> twos;
int visited[13];
int result = INF;
void dfs(int index, int cnt)
{
	if (cnt == m)
	{
		int res = 0;
		for (int i = 0; i < ones.size(); i++)
		{
			int oneX = ones[i].first;
			int oneY = ones[i].second;
			int tmpOne = INF;
			for (int j = 0; j < twos.size(); j++)
			{
				if (visited[j])
				{
					int twoX = twos[j].first;
					int twoY = twos[j].second;
					int temp = abs(twoX - oneX) + abs(twoY - oneY);
					tmpOne = min(tmpOne, temp);
				}
			}
			res += tmpOne;
		}
		result = min(res, result);
		return;
	}
	if (index == twos.size())
		return;
	visited[index] = true;
	dfs(index + 1, cnt + 1);
	visited[index] = false;
	dfs(index + 1, cnt);
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> arr[i][j];
			if (arr[i][j] == 1)
				ones.push_back({ i,j });
			else if (arr[i][j] == 2)
				twos.push_back({ i,j });
		}
	}
	dfs(0, 0);
	cout << result;
}