문제 출처

1. 문제설명

  • 크기가 NxN인 도시가 있다.
    • 각 칸은 1x1 크기의 칸으로 나눠져 있다.
  • 각 칸의 거리는 |r1-r2| + |c1-c2|



2. 알고리즘 설계

  • BFS로 각 집에서부터 치킨집의 거리를 구해야할 거 같지만 아니다.
  • BFS 문제와 달리 건물이 있든 말든 뛰어넘을 수 있다.
    • 그래서 위와 같은 거리 계산 수식을 제공한 것이다.



3. 로직

  • 집, 치킨집의 좌표를 저장해둔다.
  • 저장된 치킨집 좌표 중 M개를 고르고,
  • M개의 치킨집과 각 집의 거리를 전부 계산한다.
    • 그 중 최소 거리를 저장한다.
  • 최소 거리와 현재 저장된 정답값을 비교해 갱신한다.



4. 전체 코드

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
typedef struct { int y, x; } pos;

const int dy[] = { -1,1,0,0 };
const int dx[] = { 0,0,-1,1 };
const int SZ = 50, INF = 0x3f3f3f;
int n, m, ans, c[SZ][SZ];
bool selected[SZ];
vector<pos> house, chicken, pick;

int distance(pos a, pos b) { return abs(a.x - b.x) + abs(a.y - b.y); }

int find_min_distance() {
	int ret = 0;
	for (pos h : house) {
		int tmp = INF;
		for (pos chic : pick)
			tmp = min(tmp, distance(h, chic));
		ret += tmp;
	}
	return ret;
}

void dfs(int x, int cnt) {
	if (m == cnt) {
		int cmp = find_min_distance();
		ans = min(cmp, ans);
	}

	for (int i = x; i < chicken.size(); i++) {
		if (selected[i]) continue;

		selected[i] = true;
		pick.push_back(chicken[i]);
		dfs(i, cnt + 1);
		selected[i] = false;
		pick.pop_back();
	}
}

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

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> c[i][j];
			if (c[i][j] == 1) house.push_back({ i,j });
			if (c[i][j] == 2) chicken.push_back({ i,j });
		}
	}

	ans = INF;
	dfs(0, 0);
	cout << ans;
	return 0;
}



5. 소감

  • BFS를 워낙 많이 풀었다보니,
  • 1x1 크기의 맵이 주어지면, 자동으로 BFS로 경로를 탐색해야겠다는 생각이 든다.
  • 하지만, 당연하게도 시간초과가 발생했다.