[G5] 백준 15686번 치킨 배달 C++ 백트래킹, 브루트포스 알고리즘, 구현, 플러드필

리뷰

 

DFS + 플러드필을 조합하여 AC를 받았다, 조합 관련 가지치기가 필요한 문제 안하면 시간 초과 난다 ㅠ

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

 

전역 변수

• n, m, ans : 맵의 한 변의 길이를 저장할 변수 n, 치킨 집의 최대를 저장할 변수 m, 정답을 저장할 변수 ans
• dx, dy : 4방향 탐색을 위한 방향 배열
• lst : 맵 정보를 입력 받을 2차원 정수형 벡터
• BBQ : 치킨 집 정보를 저장할 구조체, 치킨집의 x, y좌표와 현재 이동한 거리를 d에 저장한다.
• bbqs : 치킨 집의 모든 정보를 저장할 벡터
• choose : 현재 선택한 치킨집의 인덱스를 저장할 정수형 벡터
• cnt : bbqs의 길이를 저장할 정수형 변수
• chic : 치킨 집의 중복을 방지하기 위해 사용할 치킨집 전용 방문 배열
• v : 플러드필을 할때 사용할 맵 전용 방문 배열

 

함수

1. Find

int Find(vector<vector<int>>& map)

 

플러드필을 통해 선택한 치킨집에서 집으로의 거리를 구하는 함수

1. BBQ타입 큐 q를 초기화 하고, choose배열에 선택한 인덱스의 치킨집 정보를 추가해 준다.
2. 방문 배열v를 초기화 해주고, 거리정보 dist를 0으로 초기화 해준다.
3. 큐가 빌때까지 각 치킨집의 움직임을 저장하면서 탐색을 진행해 준다.
4. 이동할때마다 d를 1씩 증가하며 만약 맵 상에서 1을 만난 경우 0으로 바꿔주고 dist에 nd값을 더해준다.
5. 탐색이 종료되었다면 dist에 저장된 값을 리턴해 준다.

2. bt

void bt(int level)

 

백트래킹을 통해 재귀적으로 치킨집을 선택하는 함수

1. 기저 조건은 현재 재귀 단계 level이 m에 도달했을 때이다.
2. 맵을 깊은 복사 해준 후 Find함수를 수행하여 리턴값을 ans와 비교해 최소값을 갱신해 준 뒤 리턴해 준다.
3. 기저조건에 해당되지 않는다면 cnt번의 for문을 개행해준다.
4. 만약 현재 인덱스의 치킨집을 선택한 상태가 아니고, 선택한 마지막 치킨집보다 인덱스가 크다면
5. 현재 인덱스를 방문처리 해주고 choose벡터에 추가해 준 뒤 재귀단계를 높여 재귀를 진행해 준다.
6. 재귀가 끝난 후엔 방문처리를 해제하고 choose벡터에서 제거해 준다.

 

문제풀이

1. n, m값을 입력 받은 뒤 lst를 n * n크기로 사이즈를 조정해 준다.
2. 맵 정보를 입력 받는다. 이때 값이 2라면 치킨집이므로 bbqs에 좌표와 거리 0을 추가해 준다.
3. cnt를 bbqs의 size로 초기화 해준 뒤 bt함수에 매개변수 0을 전달해 탐색을 수행해 준다.
4. ans에 저장된 값을 출력해 준다.

 

참고 사항

choose의 맨 뒤의 수보다 커야 중복 탐색을 진행하지 않는다.

예를 들어 인덱스가 0, 1, 2인 치킨집 탐색을 했다면 2, 1, 0인 치킨집 탐색은 결과가 동일하므로 진행할 필요가 없다.

 

 

정답 코드

#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

int n, m, ans = 2e9;
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
vector<vector<int>>lst;

struct BBQ {
	int x, y, d;
};

vector<BBQ> bbqs;
vector<int> choose;
int cnt;
int chic[14];
int v[50][50];

int Find(vector<vector<int>>& map) {
	queue<BBQ> q;
	for (int i = 0; i < m; i++) q.push(bbqs[choose[i]]);
	memset(v, 0, sizeof(v));
	int dist = 0;

	while (!q.empty()) {
		BBQ cur = q.front(); q.pop();
		int cx = cur.x, cy = cur.y, cd = cur.d;

		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i], ny = cy + dy[i], nd = cd + 1;
			if (0 <= nx && nx < n && 0 <= ny && ny < n && !v[nx][ny]) {
				v[nx][ny] = 1;
				if (map[nx][ny] == 1) {
					map[nx][ny] = 0;
					dist += nd;
				}
				q.push({ nx, ny, nd });
			}
		}
	}
	return dist;
}

void bt(int level) {
	if (level >= m) {
		vector<vector<int>> new_map = lst;
		ans = min(ans, Find(new_map));
		return;
	}

	for (int i = 0; i < cnt; i++) {
		if (chic[i]) continue;
		if (!choose.empty() && i < choose.back()) continue;
		chic[i] = 1;
		choose.push_back(i);
		bt(level + 1);
		chic[i] = 0;
		choose.pop_back();
	}
}

int main() {
	cin >> n >> m;
	lst.resize(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> lst[i][j];
			if (lst[i][j] == 2) bbqs.push_back({ i, j, 0 });
		}
	}

	cnt = bbqs.size();
	bt(0);
	cout << ans;
}