https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu
대표적인 BFS문제 입니다.(물론 기준점과 집까지의 거리 계산으로도 풀 수 있습니다.)
저 같은 경우 연산 수를 줄이기 위해 먼저 depth마다 k를 미리 계산한 후 시작했습니다.
다음은 바로 bfs를 돌렸습니다. 이 때 최대한 범위를 넓힌다해도 2n보다 작기 때문에 2n까지만 돌려줬습니다.
이 문제는 cut를 잘하는 것이 중점인 것 같습니다.
만약 문제를 푸셨다면 시간을 더 줄이는 방법을 고민하는 것도 좋을 것 같습니다.(참고로 제 코드는 대략 550ms……^^;;)
#include <iostream>
#include <queue>
using namespace std;
int map[21][21];
bool ch[21][21];
int k[41];
int n, m, result;
queue <pair<int, int>> q;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
void bfs(int profit, int homeCnt) {//(집이 내는 수익,집 갯수)
for (int cnt = 1; cnt < 2 * n; cnt++) {
int size = q.size();//큐에들어있는사이즈만큼 돌려서 k depth 계산
if (profit - k[cnt] >= 0&&result<homeCnt) result = homeCnt;//k depth늘어날때마다 result 체크
while (size--) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < n&&ny < n&&ch[nx][ny] == false) {
if (map[nx][ny] == 1) {
profit += m;//이익 추가
homeCnt += 1;//집 cnt 추가
}
ch[nx][ny] = true;
q.push(make_pair(nx, ny));
}
}
}
}
//초기화
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
ch[i][j] = false;
}
}
while (!q.empty())q.pop();
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int test_case;
cin >> test_case;
for (int i = 1; i <= 40; i++) {
k[i] = i * i + (i - 1)*(i - 1);
}
for (int t = 1; t <= test_case; t++) {
//start
result = 0;
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> map[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {//bfs 출발위치 설정하고 들어간다
ch[i][j] = true;
q.push(make_pair(i, j));
if(map[i][j]==0) bfs(0,0);
else bfs(m, 1);
ch[i][j] = false;
}
}
//end
cout << '#' << t << ' ' << result << '\n';
}
}
- 혼잣말
피곤하다.. 현재시각 밤 12시반 시간 줄이는거 하고 싶지만
내일 해야쥥