백준 15686 c++ "치킨 배달" -PlusUltraCode-

 

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

 

 

[필자 사고]

조합을 이용한 백트래킹 문제이다.

조합알고리즘에서 가장 중요하다고 생각하는 점음 아래와 같다.

1. 자신이 방문한 곳은 true 처리하고 방문이 끝나면 false처리 !!

2. 재귀를 이용하여 DFS탐색과 유사

 

그리고 이 문제에서 house의 위치를 배열에 저장해 놓고 
chicken집의 위치또한 배열에 저장해 놓은 다음 그 둘의 거리를 구하는 공식을 이용하여 

부루스트알고리즘을 사용하여 문제를 해결해 나가면 된다.

 

처음에 필자는 거리구하는 공식이 아닌 BFS탐색을 고집하여 최단거리를 찾으려고 했지만.

시간초과가 나게 되었다. 문제에서 최단거리 구하는 공식을 괜히 준게 아니라고 생각한다.

다음 부터는 문제에서 어떤 공식이 주어지면 이 공식을 활용하면 좀 더 쉽게 문제를 해결할 수 

있겠구나 와 같은 사고를 가지고 문제를 임해야 겠다.

 

아래는 소스코드 해설이다.

 

주요 변수 및 구조

• arr: 도시의 구조를 저장하는 2차원 배열.
• chicken: 치킨 가게 위치를 저장하는 벡터.
• house: 집의 위치를 저장하는 벡터.
• V: 선택된 치킨 가게의 조합을 저장하는 벡터.
• visitedChicken: 특정 치킨 가게가 선택되었는지 여부를 추적하는 방문 배열.
• N: 도시의 크기 (NxN).
• M: 선택할 치킨 가게의 수.
• resultMinNumber: 최소 치킨 거리 결과를 저장하는 변수, 초기값은 무한대.

Input() 함수

• 도시의 크기 N과 선택할 치킨 가게 수 M을 입력받는다.
• 도시 배열을 설정하고, 각 위치의 값에 따라 치킨 가게와 집을 각각 벡터에 저장한다.

calculate(int i, int k) 함수

• house[i]와 V[k] 사이의 맨해튼 거리를 계산하는 함수다.
  • 즉, 특정 집과 선택된 치킨 가게 사이의 거리를 계산하여 반환한다.

calculateDistance() 함수

• 모든 집에 대해 가장 가까운 치킨 가게와의 거리를 계산하고, 그 거리의 합을 반환하는 함수다.
  • 각 집마다 가장 가까운 치킨 가게를 찾고, 그 거리의 합을 구한다.

combination(int idx, int count) 함수

• 백트래킹을 이용해 치킨 가게의 조합을 찾는 함수다.
• M개의 치킨 가게가 선택되면, calculateDistance()를 통해 현재 선택된 치킨 가게들과 모든 집 사이의 최소 거리를 계산한다.
• 그 결과를 resultMinNumber에 저장하면서 최솟값을 갱신한다.

백트래킹 과정

• combination() 함수는 주어진 idx에서 시작해 아직 방문하지 않은 치킨 가게를 선택한다.
• 선택된 치킨 가게를 벡터 V에 추가하고, 다시 재귀적으로 다음 치킨 가게를 선택한다.
• 모든 조합을 탐색한 후, visitedChicken[i]를 false로 설정하여 다시 백트래킹한다.

GameStart() 함수

• 치킨 가게 선택 조합을 시작하는 함수로, combination(0, 0)을 호출해 조합을 탐색한다.

main() 함수

• Input()으로 데이터를 입력받고, GameStart()를 통해 게임을 시작한다.
• 마지막으로 최소 치킨 거리를 출력한다.

 

[소스 코드]

 

#include <iostream>
#include <vector>
#include <queue>
#include<climits>
#include <cmath>

using namespace std;
typedef pair<int, int> Node;

vector<vector<int>> arr;
vector<Node> chicken;
vector<Node> house;
vector<Node> V;

vector<bool> visitedChicken;

int N, M;
int resultMinNumber = INT_MAX;

void Input() {
	cin >> N >> M;
	arr.resize(N);
	visitedChicken.resize(13,false);

	for (int i = 0; i < N; i++) {
		arr[i].resize(N);
	}

	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			int num;
			cin >> num;
			if (num == 2) {
				chicken.push_back({ i,k });
				arr[i][k] = 0;
				continue;
			}
			else if (num == 1) {
				house.push_back({ i,k });
			}

			arr[i][k] = num;
		}
	}
}
int calculate(int i, int k) {
	return abs(house[i].first - V[k].first) + abs(house[i].second - V[k].second);
}

int calculateDistance() {

	int minSumNumber = 0;

	for (int i = 0; i < house.size(); i++) {
		int minNum = INT_MAX;
		for (int k = 0; k < V.size(); k++) {
			minNum = min(minNum, calculate(i, k));
		}
		minSumNumber += minNum;
	}

	return minSumNumber;
}

void combination(int idx,int count) {

	if (count == M) {
		resultMinNumber = min(resultMinNumber, calculateDistance());
		return;
	}
	
	for (int i = idx; i < chicken.size(); i++) {
		if (visitedChicken[i] == true)continue;
		visitedChicken[i] = true;
		V.push_back(chicken[i]);
		combination(i, count + 1);
		visitedChicken[i] = false;
		V.pop_back();
	}
}

void GameStart() {
	combination(0, 0);
}

int main(void) {
	Input();
	GameStart();
	cout << resultMinNumber;
}