[백준 15686] 치킨 배달

++22.11.08 갱신

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

15686번: 치킨 배달

#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
int N, M;
int board[50 + 2][50 + 2];

struct _st
{
	int x, y;
};
std::queue<_st> Q;
int visited[50 + 2][50 + 2];

std::vector<_st> Chk;
int choice[13 + 2];
int chk_cnt;
int ans = 0x7fffffff;


void input()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &board[i][j]);
			if (board[i][j] == 2) Chk.push_back({ i, j });
		}
	}
	chk_cnt = Chk.size();
}

void BFS()
{
	int dir_x[4] = { 0, 0 ,1, -1 };
	int dir_y[4] = { 1, -1, 0, 0 };

	Q = {};
	memset(visited, -1, sizeof(visited));

	for (int i = 0; i < M; i++) {
		int cx = Chk[choice[i]].x;
		int cy = Chk[choice[i]].y;
		Q.push({ cx, cy });
		visited[cx][cy] = 0;
	}

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
			if (visited[nx][ny] >= 0) continue;
			Q.push({ nx, ny });
			visited[nx][ny] = visited[data.x][data.y] + 1;
		}
	}
	//debug();
}

int get_dist()
{
	int total = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (board[i][j] == 1) total += visited[i][j];
		}
	}
	return total;
}


void DFS(int n, int s)
{
	if (n == M) {
		BFS();
		int total = get_dist();
		if (ans > total) ans = total;
		return;
	}

	for (int i = s; i < chk_cnt; i++) {
		choice[n] = i;
		DFS(n + 1, i + 1);
	}
}



int main()
{
	input();
	DFS(0, 0);	// 인풋받은 치킨집 개수 중 M개 고르기
	printf("%d\n", ans);
	return 0;
}

1. 조합 돌려서 인풋받은 치킨집 개수 중 M개를 골라준다. 

2. BFS 돌려서 각 치킨집으로 부터 집까지의 거리를 구해준다. (이때 이미 방문한 집이면 더 가까운 치킨집이 있다는 뜻이므로 continue 해준다)

3. get_dist 함수를 통해 board[i][j] == 1, 즉 집인 곳의 visited[i][j] 값을 total 변수에 저장한다. 이때 방문배열에 저장된 정보는 BFS 함수를 돌리면서 구했던, 각 집에서 가장 가까운 치킨집의 거리이다. 

---

치킨거리 구하려고 N * N 루프 돌렸던 이전 풀이..

#include <cstdio>
#include <cstdlib>
int N, M;
int house[50 * 50 + 10][2 + 2];		// 50 * 50 행렬이므로 최대 50개가 아니라 50 * 50개 ..
int chicken[50 * 50 + 10][2 + 2];
int combi[13 + 2];
int flag[13 + 2];
int numbers[13 + 2];
int h_cnt;
int c_cnt;
int tmp_total;
int total = 0x7fffffff;


void input(void)
{
	scanf("%d %d", &N, &M);
	int info = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &info);
			if (info == 1) {
				house[h_cnt][0] = i;
				house[h_cnt][1] = j;
				h_cnt++;
			}
			else if (info == 2) {
				chicken[c_cnt][0] = i;
				chicken[c_cnt][1] = j;
				c_cnt++;
			}
		}
	}
}

void get_chicken_len(void)
{
	int min = 100;	// 집 : (0, 0), 치킨집 : (49, 49)
	for (int i = 0; i < h_cnt; i++) {
		for (int j = 0; j < M; j++) {
			int tmp = abs(house[i][0] - chicken[combi[j] - 1][0]) + abs(house[i][1] - chicken[combi[j] - 1][1]);
			min = (min > tmp) ? tmp : min;	// 치킨거리
		}
		tmp_total += min;	// 해당 조합의 수에 대한 도시의 치킨 거리
		min = 100;	// 치킨거리 구하기 위해 초기화 
	}
}


void combination(int n, int r)
{
	if (n == M) {
		for (int i = 0; i < M; i++) {
			combi[i] = numbers[i];
		}
		get_chicken_len();
		total = (total > tmp_total) ? tmp_total : total;	// 최소의 도시의 치킨 거리를 구하기 위함, total과 비교하여 더 작은 값 선택
		tmp_total = 0;	// 치킨거리 구하기 위해 초기화 
	}

	for (int i = r; i < c_cnt; i++) {
		if (flag[i] == 0) {
			numbers[n] = i + 1;
			flag[i] = 1;
			combination(n + 1, i);
			flag[i] = 0;
		}
	}

}

int main()
{
	input();
	combination(0, 0);	// c_cnt 중 M개 선택
	printf("%d", total);
	return 0;
}

삽질로 하루 반나절을 쓰고... 방향찾고 또 반나절을 쓴 문제...

물론 그동안 책상앞에 앉아만 있었던건 아니고 산책도 하고 치킨도 먹고 맥주도 먹었는데... 그래도 문제 못풀면 계속 스트레스는 받잖아요 ? 토요일은 치킨 배달에 헌납함 ㅋ

 

 

// input() 함수

이번 코드는 무려 인풋 함수에서부터 집고 넘어가야할 것이 있다. 

바로 배열의 범위 ....^^ 

50 * 50 행렬에서 1이 한 개 채워질 수 있는 경우의 수는 너무나 당연하게도 50 * 50이다.

그러나 나는 이를 간과하고 어떤 패기로운 생각인지는 모르겠지만 house와 chicken의 범위를 [50 + 10][2 + 2]로 줬다. 아주 자연스럽게 0초컷으로 틀림 ㅋ

 

그리고 예제로 주어지는 전체 원소를 저장하는 것이 아니라, 집(1) 의 좌표와 치킨집(2)의 좌표를 따로따로 house 배열과 chicken 배열에 저장하였다. 이렇게 하면 나중에 거리 계산하기 편하기 때문이다. 

 

 

// combination() 함수

전체 치킨집의 개수(c_cnt)에서 M개를 선택하여 도시의 치킨거리를 구하는 함수이다. 

조합을 구하는 함수에 대한 설명은 따로 게시물을 파겠다. 

M개 선택 후 combi 배열이 완성되면, get_chicken_len() 함수를 통해 각 경우의 수에 대한 도시의 치킨 거리를 구한다. 

이를 tmp_total 변수에 저장하고, total 변수와 비교하여 더 작은 값을 채택한다. 

다음 경우의 수에 대하여 다시 도시의 치킨 거리를 구해야 하기 때문에 tmp_total을 초기화시켜주는 것도 잊지 않았다. 

 

 

// get_chicken_len() 함수

먼저 min의 초기값을 100으로 정해준 이유는 50 * 50 행렬이 들어왔을 때, (0, 0)에 집이 있고 (49, 49)에 치킨집이 있을 때가 가장 거리가 먼 경우이기 때문이다. 사실 거리의 최댓값은 49 + 49 = 98 이지만 50 + 50 = 100 으로 조금 넉넉하게 잡아 주었다. 

 

첫번째 루프는 각 집들의 위치를 탐색한다. 두번째 루프는 각 치킨집들의 위치를 탐색한다. 

"집에서 치킨집까지의 치킨거리들(tmp)" 중 최소의 값(min)을 찾아야하기 때문에, 집을 기준으로 루프를 돌려준 것이다. 

tmp를 구하는 수식에서 "combi[j] - 1"를 해준 이유는, chicken 배열을 입력받을 때 인덱스를 0부터 설정해주었기 때문이다.  3개 중에 1개를 선택하는 경우는 1, 2, 3 인데 chicken 배열에는 chicken[0], chicken[1], chicken[2] 행에 정보가 저장되어 있다는 것이다. 

이렇게 구한 min값은 tmp_total에 누적하여 각 경우의 "도시의 치킨 거리"를 구한다. 

그리고 min값은 다시 100으로 초기화하여 다음 치킨집에 대하여 치킨거리를 구할 수 있도록 한다.