문제:
14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다.
www.acmicpc.net
실수:
dfs에서 재귀함수 호출 누락
bf 탈출 조건 충족시 return!
재사용하는데 재방문을 허용하지 않는 vst -> int로 선언
코드:
전자는 빈 공간의 좌표를 1차원 배열에 저장하여
bf에서 선택지를 traverse를 할 때 1중 for문으로 처리 가능.
후자는 별도의 자료구조 없이
bf에서 map의 빈칸을 2중 for문으로 traverse
#include <iostream>
#define f(i, b, e) for(int i = (b); i < (e); ++i)
using namespace std;
int R, C;
int map[10][10];
int bl[64][2], bls;
int vr[10][2], vrs;
int vra, mvra = 64;
// dfs
int vst[9][9], v;
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };
void dfs(int r, int c) {
vst[r][c] = v;
if (!map[r][c]) ++vra;
f(d, 0, 4) {
int nr = r + dr[d], nc = c + dc[d];
if (map[nr][nc] == 1) continue;
if (vst[nr][nc] == v) continue;
dfs(nr, nc);
}
}
// bf
void bf(int bli, int s) {
if (s == 3) {
++v;
vra = 0;
f(vri, 0, vrs)
dfs(vr[vri][0], vr[vri][1]);
if (vra < mvra)
mvra = vra;
return;
}
for (; bli < bls; ++bli) {
map[bl[bli][0]][bl[bli][1]] = 1;
bf(bli + 1, s + 1);
map[bl[bli][0]][bl[bli][1]] = 0;
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> R >> C;
for (int r : { 0, R + 1 })
fill(map[r], map[r] + C + 2, 1);
f(r, 1, R + 1) {
map[r][0] = map[r][C + 1] = 1;
f(c, 1, C + 1) {
cin >> map[r][c];
switch (map[r][c]) {
case 0: bl[bls][0] = r;
bl[bls][1] = c;
++bls; break;
case 2: vr[vrs][0] = r;
vr[vrs][1] = c;
++vrs; break;
}
}
}
bf(0, 0);
cout << bls - mvra - 3;
return 0;
}#include <iostream>
#define f(i, b, e) for(int i = (b); i < (e); ++i)
using namespace std;
int R, C;
int map[10][10];
int bls;
int vr[10][2], vrs;
int vra, mvra = 64;
// dfs
int vst[9][9], v;
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };
void dfs(int r, int c) {
vst[r][c] = v;
if (!map[r][c]) ++vra;
f(d, 0, 4) {
int nr = r + dr[d], nc = c + dc[d];
if (map[nr][nc] == 1) continue;
if (vst[nr][nc] == v) continue;
dfs(nr, nc);
}
}
// bf
void bf(int r, int c, int s) {
if (s == 3) {
++v;
vra = 0;
f(vri, 0, vrs)
dfs(vr[vri][0], vr[vri][1]);
if (vra < mvra)
mvra = vra;
return;
}
for(; r <= R; ++r) {
for (; c <= C; ++c) {
if (map[r][c]) continue;
map[r][c] = 1;
bf(r, c, s + 1);
map[r][c] = 0;
}
c = 0;
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> R >> C;
for (int r : { 0, R + 1 })
fill(map[r], map[r] + C + 2, 1);
f(r, 1, R + 1) {
map[r][0] = map[r][C + 1] = 1;
f(c, 1, C + 1) {
cin >> map[r][c];
switch (map[r][c]) {
case 0: ++bls; break;
case 2: vr[vrs][0] = r;
vr[vrs][1] = c;
++vrs; break;
}
}
}
bf(0, 0, 0);
cout << bls - mvra - 3;
return 0;
}