15686번: 치킨 배달
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는
www.acmicpc.net
설계
선택된 치킨집들로부터의 최소비용
브루트포스로 M개의 치킨집들을 선택하되, 매번 치킨집을 선택할 때마다 해당 좌표에서 BFS를 실행한다. BFS에서 방문 여부를 체크하는 대신 지도 크기만큼 비용 배열 선언하고, 방문할 칸의 비용을 절약할 수 있는 경우에만 방문한 후 해당 좌표의 비용을 갱신한다. M개의 치킨집이 모두 선택되면 최소비용 배열이 완성된다.
디버깅
더보기
- unsigned int cst[0] 배열을 -1(INT_MAX)로 초기화하기
- unsigned int asn를 -1(INT_MAX)로 초기화하기
개선점
지도에 장애물 등이 있는 경우가 아니기 때문에, 좌표만 알면 탐색 없이 공식으로 거리를 간단히 구할 수 있다. 탐색을 사용하지 않고 해결해보자.
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
int N, M;
int map[50][50];
unsigned int cst[14][50][50], ncst[50][50];
int chk[2500][2], chkn;
int sel[13];
unsigned int ans = -1;
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };
void BFS(int r, int c, int s) {
cst[s][r][c] = 0;
queue<pair<int, int>> q;
q.emplace(r, c);
int t = 1;
while (!q.empty()) {
int qs = q.size();
while (qs--) {
int r = q.front().first, c = q.front().second;
q.pop();
for (int d = 0; d < 4; ++d) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || N <= nr || nc < 0 || N <= nc || cst[s][nr][nc] <= t) {
continue;
}
cst[s][nr][nc] = t;
q.emplace(nr, nc);
}
}
++t;
}
}
void BF(int i, int s) {
if (s == M) {
int dst = 0;
for (int r = 0; r < N; ++r) {
for (int c = 0; c < N; ++c) {
if (map[r][c] == 1) {
dst += cst[M][r][c];
}
}
}
if (dst < ans) {
ans = dst;
}
return;
}
for (; i < chkn; ++i) {
sel[s] = i;
memcpy(cst[s + 1], cst[s], sizeof(int) * 50 * 50);
BFS(chk[i][0], chk[i][1], s + 1);
BF(i + 1, s + 1);
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> M;
for (int r = 0; r < N; ++r) {
for (int c = 0; c < N; ++c) {
cin >> map[r][c];
if (map[r][c] == 2) {
chk[chkn][0] = r;
chk[chkn][1] = c;
++chkn;
}
}
}
memset(cst[0], -1, sizeof(int) * 50 * 50);
BF(0, 0);
cout << ans;
return 0;
}