[백준 14502] 연구소 (BFS)

문제출처: 

https://www.acmicpc.net/problem/14502

풀이

제 코드의 실행시간이 잘 푸신분들에 비해 최대 6배 차이가량납니다. 이해가 어려워서 이 글을 보러오신거면 제 코드를 보고 다른 빠른풀이법을 보시면좋을것같아요.(그분들 코드가 많이 어렵더라구요..) 

제 코드상에서 실행시간을 줄일 수 있을만한 요소에 대해 알고계신분들은 댓글로 지적좀해주세요..

대충 머릿속으로는 구상이되는데 막상 구현할때 벽3개를놓고 연산하는 시뮬레이션과정이 너무어려워서 다른분들의 코드를 조금 참조했습니다...

백트래킹 기법도 쓰이는데, 제 생각에 dfs,bfs문제중에 어려운문제는 거의 백트래킹+브루트포스+dfs or bfs 같네요.. 어렵습니다.

글로써봤자 이해가 안가니 주석과 코드를 보고 흐름을 따라가보시면 이해가편할 것 같습니다.

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
//벽을 세움
//벽3개를세움
//벽3개를 세울 때 bfs,
//그 bfs를돌렷을때 각 최댓값비교
int map[8][8];
int temp[8][8];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { -1,1,0,0 };
int n, m, area;
void make_wall(int wall);
void bfs();
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> map[i][j];

	//비어있는공간있을떄 그떄 temp로복사받음
	//비어있는 공간,그 자리에서부터 벽3개를 놓는 시늉을 다 돌림
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (map[i][j] == 0)
			{
				for (int i = 0; i < n; i++)
					for (int j = 0; j < m; j++)
						temp[i][j] = map[i][j];

				//현재 자리에 벽세움
				temp[i][j] = 1;
				make_wall(1);
				//다시원상복구
				temp[i][j] = 0;
			}
			
		}
	}
	cout << area << '\n';
}
void make_wall(int wall)
{
	//벽3개 만들었으면 bfs돌림
	if (wall == 3)
	{
		bfs();
		return;
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			//좌표가 0이면
			if (temp[i][j] == 0)
			{
				//벽을 세우고
				temp[i][j] = 1;
				//벽을 한칸늘렸으니 3개인지확인
				make_wall(wall + 1);
				//위의함수로 그자리에서 모든연산끝났으니 다시 0으로,
				temp[i][j] = 0;
			}
		}
	}
}
void bfs()
{
	//temp변수로 갖고놀면 virus가 퍼질떄 temp가 수정되므로 다시 배열복사
	int virus[8][8];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			virus[i][j] = temp[i][j];

	queue<pair<int, int>>q;
	//바이러스좌표를 저장하여 퍼뜨림
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (virus[i][j] == 2)
				q.push({ i,j });

	//퍼뜨려서,
	//최종적으로 map에서 0인 현재좌표에서
	//벽3개를 가정하고, 퍼뜨렸을 때 최대안전영역구함
	while (!q.empty())
	{
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (nx >= 0 && ny >= 0 && nx < m && ny < n)
			{
				if (virus[ny][nx] == 0 )
				{
					virus[ny][nx] = 2;
					q.push({ ny,nx });
				}
			}
		}
	}
	//최대영역구하기
	int cnt = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (virus[i][j] == 0)
				cnt++;
		}
	}
	area = max(area, cnt);
}

결과