백준 15686번 : 치킨 배달

문제 링크 : www.acmicpc.net/problem/15686

내 풀이1(2021.1.28.) : BFS, 조합

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <limits.h>

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

vector<int_pair> list;
vector<int> index;
int map[51][51];
int visit[51][51];
int N, M;
int cnt = 0;
int mi = INT_MAX;

void initialize_visit() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			visit[i][j] = 0;
		}
	}
}

void show() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cout << map[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

int bfs(int sy, int sx) {
	int dy[] = { 0,0,-1,1 };
	int dx[] = { -1,1,0,0 };
	queue<int_pair> q;
	q.push(make_pair(sy, sx));
	visit[sy][sx] = 1;

	int cnt = -1;
	while (!q.empty()) {
		int sz = q.size();
		cnt++;
		for (int j = 0; j < sz; j++) {
			int_pair p = q.front(); q.pop();
			int y = p.first;
			int x = p.second;
			if (map[y][x] == 2) {
				initialize_visit();
				return cnt;
			}

			for (int i = 0; i < 4; i++) {
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (ny <= 0 || nx <= 0 || ny > N || nx > N) continue;
				if (visit[ny][nx] == 1) continue;
				q.push(make_pair(ny, nx));
				visit[ny][nx] = 1;
			}
		}
	}
}

void combination(vector<int>& index, int n, int r) {
	vector<int> selection;
	for (int i = 0; i < r; i++) selection.push_back(1);
	for (int i = 0; i < n - r; i++) selection.push_back(0);

	do {
		for (int i = 0; i < index.size(); i++) {
			if (selection[i] == 1) {
				int y = list[index[i]].first;
				int x = list[index[i]].second;
				map[y][x] = 2;
			}
		}

		int total = 0;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (map[i][j] != 1) continue;
				total += bfs(i, j);
			}
		}
		mi = min(mi, total);

		for (int i = 0; i < index.size(); i++) {
			if (selection[i] == 1) {
				int y = list[index[i]].first;
				int x = list[index[i]].second;
				map[y][x] = 0;
			}
		}
	} while (prev_permutation(selection.begin(), selection.end()));
}

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

	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int temp; cin >> temp;
			if (temp == 2) {
				cnt++;
				list.push_back(make_pair(i, j));
			}
			else map[i][j] = temp;
		}
	}

	for (int i = 0; i < cnt; i++) {
		index.push_back(i);
	}

	combination(index, cnt, M);

	cout << mi;

	return 0;
}

결과 : 시간 초과

BFS로 풀 필요 없는 문제였다. 거리를 구할 때, 단순히 뺄셈의 절댓값을 계산하면 되기 때문이다.

조합으로 푸는 문제인데, 조합은 나처럼 STL의 permutation을 이용해도 되지만, DFS를 이용할 수도 있다고 한다.

참고로, 순열과 조합 모두 DFS로 구현할 수 있다고 한다.

 

참고1 : jaimemin.tistory.com/1059

참고2 : data-make.tistory.com/355

 

풀이에 참고한 링크 : www.acmicpc.net/board/view/55130

내 풀이2(2021.1.28.) : 조합

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits.h>
#include <cstdlib>

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

vector<int_pair> list;
vector<int> index;
int map[51][51];
int N, M;
int cnt = 0;
int mi = INT_MAX;

void combination(vector<int>& index, int n, int r) {
	vector<int> selection;
	for (int i = 0; i < r; i++) selection.push_back(1);
	for (int i = 0; i < n - r; i++) selection.push_back(0);
	do { // 특정 맵에 대하여
		int total = 0;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (map[i][j] != 1) continue;
				int m = INT_MAX;
				for (int k = 0; k < index.size(); k++) { // 선택된 r개의 치킨집에 대하여
					if (selection[k] == 1) { // 선택된 1개의 치킨집에 대하여
						int y = list[index[k]].first;
						int x = list[index[k]].second;
						m = min(m, abs(y - i) + abs(x - j));
					}
				}
				total += m;
			}
		}
		mi = min(mi, total);
	} while (prev_permutation(selection.begin(), selection.end()));
}

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

	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int temp; cin >> temp;
			if (temp == 2) {
				cnt++;
				list.push_back(make_pair(i, j));
			}
			else map[i][j] = temp;
		}
	}

	for (int i = 0; i < cnt; i++) {
		index.push_back(i);
	}
	combination(index, cnt, M);
	
	cout << mi;

	return 0;
}

결과 : 성공

사실 내 풀이처럼 맵을 그릴 필요도 없는 문제였다.

1의 좌표와 2의 좌표들을 벡터에 담기만 하면 풀 수 있다고 한다.