막혔던 점
-처음에는 dfs로 모든 core마다 방향을 정하고 bfs로 하려고 했으나 시간 초과
해결책
-dfs로 모든 core마다 4방향마다 연결가능할 때->전선표시->dfs(idx+1,coreDone+1)->전선초기화
연결 불가능할 때->dfs(idx+1,coreDone)
주의할 점
-무조건 answer을 최소값으로 갱신하는 것이 아니다.
maxDone을 갱신할 때 기존의 answer이 temp보다 더 작을 수 있다.
그래서 maxDone이 같을 때만 최소값으로 갱신한다.
#include <iostream>
#include <vector>
using namespace std;
int T, N;
int coreNum;
int maxDone;
int cell[13][13];
int answer;
void dfs(int count, int done, vector<pair<int, int>> v) {
if (count == coreNum) {
int temp = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (cell[i][j] == 2)
temp++;
}
}
if(done>maxDone){
maxDone=done;
answer=temp;
}
else if(done==maxDone) answer=answer<temp?answer:temp;
return;
}
int y = v[count].first;
int x = v[count].second;
if (y == 0 || y == N - 1 || x == 0 || x == N - 1)
dfs(count + 1, done + 1, v);
else {
//상
bool flag = true;
for (int i = 0; i < y; i++) {
if (cell[i][x] != 0) {
flag = false;
break;
}
}
if (flag) {
for (int i = 0; i < y; i++) {
cell[i][x] = 2;
}
dfs(count + 1, done + 1, v);
for (int i = 0; i < y; i++) {
cell[i][x] = 0;
}
}
//하
flag = true;
for (int i = y + 1; i < N; i++) {
if (cell[i][x] != 0) {
flag = false;
break;
}
}
if (flag) {
for (int i = y + 1; i < N; i++)
cell[i][x] = 2;
dfs(count + 1, done + 1, v);
for (int i = y + 1; i < N; i++)
cell[i][x] = 0;
}
//좌
flag = true;
for (int i = 0; i < x; i++) {
if (cell[y][i] != 0) {
flag = false;
break;
}
}
if (flag) {
for (int i = 0; i < x; i++)
cell[y][i] = 2;
dfs(count + 1, done + 1, v);
for (int i = 0; i < x; i++)
cell[y][i] = 0;
}
//우
flag = true;
for (int i = x + 1; i < N; i++) {
if (cell[y][i] != 0) {
flag = false;
break;
}
}
if (flag) {
for (int i = x + 1; i < N; i++)
cell[y][i] = 2;
dfs(count + 1, done + 1, v);
for (int i = x + 1; i < N; i++)
cell[y][i] = 0;
}
dfs(count + 1, done, v);
}
}
int main(void) {
cin >> T;
for (int casenum = 1; casenum <= T; casenum++) {
cin >> N;
vector<pair<int, int>> core;
coreNum = 0;
maxDone = 0;
answer = 200;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
cell[i][j] = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> cell[i][j];
if (cell[i][j] == 1) {
coreNum++;
core.push_back({ i,j });
}
}
}
dfs(0, 0, core);
cout << "#" << casenum << " " << answer << "\n";
}
}
'Algorithm > SWEA' 카테고리의 다른 글
[SWEA] 3000. 중간값 구하기 (0) | 2022.02.10 |
---|---|
[SWEA] 3304 최장 공통 부분 수열 (0) | 2022.02.07 |
[SWEA] 1868. 파핑파핑 지뢰찾기 (0) | 2022.01.31 |
[SWEA] 1251. 하나로 (0) | 2022.01.28 |
[SWEA] 1249. 보급로 (0) | 2022.01.28 |