Baekjoon14502-연구소

백준 사이트 14502 - 연구소 문제입니다.

1. 문제

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

---

2. Input , Output

---

3. 분류 및 난이도

BFS문제입니다.
아마 삼성기출문제로 나왔던걸로 기억합니다.
백준에서는 Gold5난이도를 책정하고 있습니다.

---

4. 생각한 것들

• 벽 3개를 세워야하는데 맵의 최대 크기가 8 * 8 로 크지 않아서 3중 for문으로 넣어도 됩니다.

  저 같은경우 2차원 맵에 3개의 데이터를 돌아가면서 조작한다는게 익숙하지 않아 고생했습니다.  
  물론 그게 이 문제를 헤쳐나가는데의 키 포인트인 것 같습니다.  
  bfs 자체로는 어렵지 않습니다.
  

• 벽 3개를 꼭 세워야합니다.

  3 3
  0 0 0
  1 1 1
  2 2 2
  result : 0입니다.
  

• 과정을 머릿속에 생각했습니다.
  1. MAP을 만든다.
  2. 벽 3개를 세우고 바이러스를 뿌려야하기 때문에 이전 맵에 대한 정보가 필요합니다. 따라서 원본 맵의 정보를 갖고 있는 임시 맵을 생성합니다.
  3. 맵에서 0(빈공간)의 갯수를 세주되, 이것 또한 벽이 세워졌을 때 마다의 값에 대한 정보를 갖고 비교를 해야하므로 신경써줘야 했습니다.
  4. 벽을 세우기 위한 인덱스 범위를 잘 조절해주어야합니다. 간혹 벽 3개가 같은 곳에 세워지는 경우 등을 조심했습니다.

---

5. code

주석이 없는 것

#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAX = 8;

int N, M;
int arr[MAX][MAX];
bool v[MAX][MAX] = { false };
int result = 0;

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

void Input()
{
	cin >> N >> M;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
			cin >> arr[i][j];
	}
}
void checknum()
{
	result = 0;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
			if (arr[i][j] == 0)
			{
				++result;
			}
	}
}
//바이러스를 퍼트리기 위한
void bfs()
{
	memset(v, false, sizeof(v));
	queue<pair<int, int>> q;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			if (arr[i][j] == 2)
			{
				q.push(make_pair(i, j));
				v[i][j] = true;
			}
		}
	}

	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;

		q.pop();
		for (int k = 0; k < 4; ++k)
		{
			int newX = x + dx[k];
			int newY = y + dy[k];
			if (0 <= newX && newX < N && 0 <= newY && newY < M && arr[newX][newY] != 1 && v[newX][newY] != true)
			{
				q.push(make_pair(newX, newY));
				v[newX][newY] = true;
				arr[newX][newY] = 2;
			}
		}
	}
	checknum();

}
void make_wall(int x, int y)
{
	int temp[MAX][MAX];
	//복사 해두기
	memcpy(temp, arr, sizeof(arr));
	int wall = 0;
	int wall2 = 0;
	int wall3 = 0;
	for (int i = 0; wall < N; ++i)
	{
		if (i >= M)
		{
			i = 0;
			wall++;
			if (wall >= N)
				break;
		}
		wall2 = wall;
		if (arr[wall][i] != 0)
			continue;
		for (int j = i + 1; wall2 < N; ++j)
		{
			if (j >= M)
			{
				j = 0;
				wall2++;
				if (wall2 >= N)
					break;
			}
			wall3 = wall2;
			if (arr[wall2][j] != 0)
				continue;

			for (int k = j + 1; wall3 < N; ++k)
			{
				if (k >= M)
				{
					k = 0;
					wall3++;
					if (wall3 >= N)
						break;
				}
				if (arr[wall3][k] != 0)
					continue;

				arr[wall][i] = 1;
				arr[wall2][j] = 1;
				arr[wall3][k] = 1;
				int resultbefore = result;
				bfs();
				result = max(result, resultbefore);
				memcpy(arr, temp, sizeof(temp));
			}
			wall3 = wall2;
		}
		wall2 = wall;
	}
}

void Solve()
{
	//input data
	Input();
	//make wall
	make_wall(0, 0);
	cout << result;


}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	Solve();
}

주석이 있는 것

#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAX = 8;

int N, M;
//직접 조작할 배열
int arr[MAX][MAX];
//방문 기록
bool v[MAX][MAX] = { false };
//결과
int result = 0;
//좌표 이동
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };

//배열을 출력하기 위한 함수 -> 불필요
void printma()
{
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
			cout << arr[i][j] << " ";
		cout << '\n';
	}
}

void Input()
{
	cin >> N >> M;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
			cin >> arr[i][j];
	}
}
//빈공간의 갯수를 세주는 함수.
void checknum()
{
	result = 0;
	for (int i = 0; i < N; ++i)
	{
		for(int j=0;j<M;++j)
			if (arr[i][j] == 0)
			{
				++result;
			}
	}
	//cout << "result : " << result<<'\n'; 각 인덱스의 result를 검사해주기 위한 구문
}
//바이러스를 퍼트리기 위한
void bfs()
{
    //방문기록을 초기화 해주고 바이러스인 것은 다 큐에 넣습니다.
	memset(v, false, sizeof(v));
	queue<pair<int, int>> q;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			if (arr[i][j] == 2)
			{
				q.push(make_pair(i, j));
				v[i][j] = true;
			}
		}
	}

	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;

		q.pop();
		for (int k = 0; k < 4; ++k)
		{
			int newX = x + dx[k];
			int newY = y + dy[k];
			if (0 <= newX && newX < N && 0 <= newY && newY < M && arr[newX][newY] !=1 && v[newX][newY] != true)
			{
				q.push(make_pair(newX, newY));
				v[newX][newY] = true;
				arr[newX][newY] = 2;
			}
		}
	}
    //바이러스가 다 퍼졌으면 빈공간의 갯수를 세줍니다
	checknum();
	
}
void make_wall(int x,int y)
{
    //원본 배열을 복사하기 위한 배열
	int temp[MAX][MAX];
	//복사 해두기
	memcpy(temp, arr, sizeof(arr));
    //wall은 첫 번째 벽의 세로축 값 wall2 ... 
	int wall = 0;
	int wall2 = 0;
	int wall3 = 0;
		for (int i = 0; wall<N; ++i)
		{
			if (i >= M)
			{
				i = 0;
				wall++;
				if (wall >= N)
					break;
			}
            //왼쪽 위에서부터 오른쪽 아래로 훑어버려야하므로 wall2가 wall보다 작은 경우는 없음.
            //하지만 커질 경우는 많다. 매번 이렇게 초기화 해줘야 오류가 안남.
            //ex) wall이 2이고 wall2가 4인 경우 밑의 for문을 돌고 wall2가 3인경우를 안돌아서 오류가 나는 경우가 있다.
			wall2 = wall;
			if (arr[wall][i] != 0)
				continue;
			for (int j = i + 1;wall2<N; ++j)
			{
				if (j >= M)
				{
					j = 0;
					wall2++;
					if (wall2 >= N)
						break;
				}
				wall3 = wall2;
				if (arr[wall2][j] != 0)
					continue;
				
				for (int k = j + 1;wall3<N; ++k)
				{
					if (k >= M)
					{
						k = 0;
						wall3++;
						if (wall3 >= N)
							break;
					}
					if (arr[wall3][k] != 0)
						continue;
					
					arr[wall][i] = 1;
					arr[wall2][j] = 1;
					arr[wall3][k] = 1;
					int resultbefore = result;
					bfs();
					result = max(result, resultbefore);
                    /*
                    i와 j와 k가 잘 들어갔는지, 그에 따른 wall,wall2,wall3를 초기화
                    */
					//cout << i << j << k << '\n';
					//cout << wall << wall2 << wall3 << '\n';
					//cout << '\n';
                    
                    //arr에 다시 원본 데이터를 넣어줌.
					memcpy(arr, temp, sizeof(temp));
				}
                //사실 위에 초기화를 해줘서 필요없을 것 같은데 잘 모르겠음.
				wall3 = wall2;
			}
			wall2 = wall;
		}
}

void Solve()
{
	//input data
	Input();
	//make wall
	make_wall(0, 0);
	cout << result;
	

}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	Solve();
}

---

6. 후기

이 문제를 풀기 위해서 꽤 많은 시간을 투자했다.
다시 첨부터 풀어본 게 한 3번은 되는 듯.. 따지고보면 어렵지는 않지만 3중 for문을 이용해 2차원 배열을 조작한다는 것은 너무 머리 아팠다.