대엉코딩

www.acmicpc.net/problem/15686

1. 풀이방법

- 문제를 꼼꼼히 읽고, 전체 치킨 집 중에서 M개를 선택하는 경우의 수 (조합)

- 을 구해서 그 CASE마다 도시의 치킨거리를 구해보면 되는 문제.

2. 주의할점

- 딱히없음.

3.나의 코드

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

int N, M;
int map[51][51];
vector<pair<int, int>> chikenstore; //전체 치킨집을 저장할 좌표 집합
vector<pair<int, int>> chosenstore; //선택된 치킨집을 저장할 좌표 집합(M개)
vector<pair<int, int>> home; //집의 위치를 저장할 좌표 집합 (x,y) 
vector<int> result; //결과

void InputMap() { //입력받는 함수
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> map[i][j];
			if (map[i][j] == 2) {
				pair<int, int> tmp;
				tmp.first = i; tmp.second = j;
				chikenstore.push_back(tmp);
			}
			else if (map[i][j] == 1) {
				pair<int, int> tmp;
				tmp.first = i; tmp.second = j;
				home.push_back(tmp);
			}
		}
	}
}

int abs(int num1, int num2) { //절대값 반환
	if (num1 - num2 > 0) { return num1 - num2; }
	else { return num2 - num1; }
}

int loadsum(int x1, int y1, int x2, int y2) { //거리 계산
	return abs(x1, x2) + abs(y1, y2);
}

void caculatechickenload() { //도시의 치킨거리를 계산
	int sum = 0;
	for (int i = 0; i < home.size(); i++) { //집마다
		int min = 3000;
		for (int j = 0; j < chosenstore.size(); j++) { //치킨집에 대하여 거리계산(가장 가까운 치킨집=치킨거리)
			if (min > loadsum(home[i].first, home[i].second, chosenstore[j].first, chosenstore[j].second)) {
				min = loadsum(home[i].first, home[i].second, chosenstore[j].first, chosenstore[j].second);
			}
		}
		sum += min;
	}
	result.push_back(sum);
}

void Mchickenstore(int index) {
	if (chosenstore.size() == M) { // M개를 골랐다면 치킨거리계산 시작
		caculatechickenload();
		return;
	}
	for (int i = index; i < chikenstore.size(); i++) { //조합 경우의 수
		chosenstore.push_back(chikenstore[i]);
		Mchickenstore(i + 1);
		chosenstore.pop_back();
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	InputMap();
	Mchickenstore(0);
	sort(result.begin(), result.end()); //가장 최소 도시치킨거리 출력
	cout << result[0] << "\n";
	
	return 0;
}

0. 시작에 앞서...

- 만약, 그래프가 가중치가 모두 같은 간선들로 이루어져 있다면 BFS(넓이 우선탐색)을 통하여 쉽게

   최단거리를 구할 수 있다.

- 오늘은 가장 유명한 최단거리 구하는 알고리즘인 다익스트라 알고리즘에 대하여 알아보겠다.

1. Shortest-Path 정의

- 그래프 G=(V,E,W)에서 P는 nonempty-path이라 하자

- W(P) (Weight of P) = the sum of the weights (각 간선들의 가중치의 합)  이다.

- 만약 x=y (즉 같은 정점) 사이의 가중치는 0 이다.

- x정점과 y정점사이에 W(P)보다 가중치가 작은 path가 없다면 이 경로가

    shortest-path or minimum-weight path이다

2.Properties of Shortest Paths

- Lemma: shortest path property

- 간단하게 말하면 최단경로는 최단경로들로 구성되어있다 라는 것.

- 이는 귀류법으로 손쉽게 증명할 수 있다.

- if) P가 최단경로가 아니거나 Q가 최단경로가 아니라면(즉, 위 그림처럼 P'가 존재)

           W(P')<W(P)이고 W(P')+W(Q)<W(P)+W(Q) 즉 R이 최단경로가 아니다.

3. Dijkstra's Algorithm(다익스트라 알고리즘)

- Weight are nonnegative (가중치는 음수가 아니여야한다.)

- greedy 알고리즘 이기도 하며 dynamic programming 알고리즘 이기도 하다.

- 기본적인 구조는 prim 알고리즘과 비슷하다.

4.Example

- 가중치가 같다면 알파벳 순서로 선택한다고 가정.

(1) A-출발점

(2) 가중치가 가장 짧은 간선 2를 선택 결과 테이블 UPDATE

(3) AG(3)을 선택

(4) BC(4)를 선택

(.....) 이런식으로 테이블을 업데이트 해서 끝나면 A점으로 부터 다른 정점들로의

최단거리를 테이블에서 불러오기만 하면 된다.

5.Correctness

- 새로운 경로가 나타날 수 도 있는데 최단경로를 이렇게 확정해버려도 되는가?

- 간선의 가중치는 음수가 아니므로 새로운 경로가 나타도 같을 순 있어도, 

   더 짧은 경로가 나타날 순 없다.

6.분석(Analysis)

- 힙자료구조를 이용한 우선순위 큐 사용시 시간복잡도는 O(mlogm) = O(mlogn)

이라 할 수 있습니다.