백준 14502 연구소

설마 모든 좌표에 대해서 3개의 벽을 세운뒤 BFS로 문제가 해결될 줄 몰랐다.

맵의 크기가 작기 때문에 가능했다.

DFS를 보통 x,y,len 이런식의 파라미터를 넣는게 익숙하다 보니 습관적으로 문제를 정확히 분석하기 보다는

습관대로 파라미터를 만들어 놓고 시작하는데 좋지 않은 습관인듯하다.

복습할 때 DFS 활용 방식을 꼭 눈여겨 보자.

코드:

#include <iostream>

#include <queue>

#include <stdio.h>

using namespace std;

int N, M;

int map[9][9];

int map2[9][9];

int px[4] = { -1, 0, 1, 0 };

int py[4] = { 0, -1, 0, 1 };  // up left down right

int cnt;

int num_1;

int num_2;

int ans;

struct pos{

int x;

int y;

};

queue<pos> Q;

void MC(int(*a)[9], int(*b)[9]){

for (int i = 0; i <= N; i++) {

for (int j = 0; j <= M; j++) {

a[i][j] = b[i][j];

}

}

}

int max(int a, int b){

return a > b ? a : b;

}

void bfs(){

int tmp[9][9];

MC(tmp, map2);

for (int i = 1; i <= N; i++){

for (int j = 1; j <= M; j++){

if (tmp[i][j] == 2){

Q.push({ i, j });

}

}

}

while (!Q.empty()){

int nx = Q.front().x;

int ny = Q.front().y;

Q.pop();

for (int i = 0; i < 4; i++){

int x_ = px[i] + nx;

int y_ = py[i] + ny;

if (x_ > N || y_ > M || x_ < 1 || y_ < 1) continue;

if (tmp[x_][y_] == 0){

tmp[x_][y_] = 2;

Q.push({ x_, y_ });

}

}

}

int cnt = 0;

for (int i = 1; i <= N; i++){

for (int j = 1; j <= M; j++){

if (tmp[i][j] == 0)

cnt++;

}

}

ans = max(ans, cnt);

}

void dfs(int len){

if (len == 3){

bfs();

return;

}

for (int i = 1; i <= N; i++){

for (int j = 1; j <= M; j++){

if (map2[i][j]==0){

map2[i][j] = 1;

dfs(len+1);

map2[i][j] = 0;

}

}

}

}

int main(){

cin >> N >> M;

for (int i = 1; i <= N; i++){

for (int j = 1; j <= M; j++){

cin >> map[i][j];

if (map[i][j] == 2){

Q.push({ i, j });

}

}

}

for (int i = 1; i <= N; i++){

for (int j = 1; j <= M; j++){

if (map[i][j] == 0){

MC(map2, map);

map2[i][j] = 1;

dfs(1);

map2[i][j] = 0;

}

}

}

cout << ans;

system("pause");

return 0;

}