BaekJoon 2636번: 치즈(C++)

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

2636번: 치즈

풀이법

1) 방문한 곳을 체크하는 visited배열과 BFS기반의 알고리즘으로 문제를 해결했다.

2) 입력값인 arr배열에 직접적으로 값을 변경하면 bfs 알고리즘 내에서 문제가 생길 수 있기에 arr2배열을 만들어서 바뀌는 입력값을 일시적으로 담았다가 추후에 다시 arr배열로 바꾸어 주었다.

3) 모든 치즈가 녹는 경우를 확일할 수 있는 allVisited 함수를 만들어 두어 이를 while문에 활용하였고, bfs 이후에는 방문했던 곳을 표시하는 visited배열을 초기화 해주었다.

4) BFS내에서는 index 내에서 움직일 수 있는 값 중, 0인 것들은 서로 연결시키며 확인하였고, 갈 수 있는 곳 중 공기와 밀접한 면이 있는 곳(1)인 경우에는 방문하지 않았고, 현재 값이 0 인 곳만 배열을 바꾸어 줌으로서 문제를 해결하였다.

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <queue>
#include <cstring>
#define INF 987654321
using namespace std;

int n, m;
int arr[101][101];
int arr2[101][101];
bool visited[101][101];
bool visitedOne[101][101];
int vx[4] = { 1,0,0,-1 };
int vy[4] = { 0,1,-1,0 };
int last = 0;
int bfs(int a, int b)
{
	visited[a][b] = true;
	queue < pair<int, pair<int, int>>> q;
	q.push({ a,{b,0} });
	last = 0;
	while (!q.empty())
	{
		int nowX = q.front().first;
		int nowY = q.front().second.first;
		int cnt = q.front().second.second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nextX = nowX + vx[i];
			int nextY = nowY + vy[i];
			if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= m)
				continue;
			if (arr[nextX][nextY] == 0 && !visited[nextX][nextY])
			{
				visited[nextX][nextY] = true;
				q.push({ nextX,{nextY,0} });
			}
			else if (arr[nextX][nextY] == 1 && !visitedOne[nextX][nextY] && cnt == 0)
			{
				last++;
				visitedOne[nextX][nextY] = true;
				arr2[nextX][nextY] = 0;
			}
		}

	}
	return last;
}
void arrCopy()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			arr[i][j] = arr2[i][j];
			visitedOne[i][j] = false;
			visited[i][j] = false;
		}
	}
}
bool allVisited()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (arr[i][j] == 1)
				return false;
		}
	}
	return true;
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> m;
	int count = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> arr[i][j];
			arr2[i][j] = arr[i][j];
		}
	}
	int temp = 0;
	while (!allVisited())
	{
		count++;
		temp=bfs(0, 0);// 현재 빈 공간 체크
		arrCopy();
	}
	cout << count << "\n";
	cout << temp<<"\n";

}