백준 2636번 치즈(C++)

문제

정답 코드

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

using namespace std;
int n,m;
#define X second
#define Y first
/*
입력 ->
변경 맵과 이전 백업맵 2개로 생김
이전 백업맵에서 bfs를 하는데 4방향 탐색중 0이 있다면 그 부분의
변경맵을 0으로 변경
그렇게 쭉 한바퀴를 다 돌고 나면 변경 맵을 검사해서 전부다 0인지 확인
전부다 0이면 이전 백업을 출력
아니라면 백업을 바꾼 맵으로 바꾸고
다시 함수 시작.
*/

const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};
int check_done(vector<vector<int>> ar)
{
	for (int i=0;i < n;i++)
	{
		for (int j=0; j < m;j++)
		{
			if (ar[i][j] != 0)
				return(1);
		}
	}
	return (0);
}

void	print(vector<vector<int>> ar)
{
	int cnt = 0;
	for(int i=0; i < n; i++)
	{
		for (int j=0;j < m;j++)
		{
			if (ar[i][j] ==1)
				cnt++;
		}
	}
	cout << cnt <<"\n";
}

void	map(vector<vector<int>> &arr)
{
	vector<vector<int>> change = arr;
	queue<pair<int,int>> Q;
	int cnt =0;
	while (check_done(change))
	{
		vector vis(n,vector<int>(m,0));
		arr = change;
		vis[0][0] = 1;
		Q.push({0,0});
		while (!Q.empty())
		{
			auto it = Q.front();
			Q.pop();
			for (int k=0;k < 4;k++)
			{
				if (it.X +dx[k] < 0 || it.Y + dy[k]<0 ||it.X +dx[k] >=m || it.Y + dy[k] >= n)
				{
					// change[it.Y][it.X] = 0;
					continue;
				}
				if (vis[it.Y + dy[k]][it.X +dx[k]] == 1)
					continue;
				if (arr[it.Y + dy[k]][it.X +dx[k]] == 1)
				{
					change[it.Y+dy[k]][it.X+dx[k]] = 0;
					continue;
				}

				vis[it.Y + dy[k]][it.X +dx[k]]=1;
				Q.push({it.Y+ dy[k], it.X+dx[k]});
			}
		}
		cnt++;
	}
	cout << cnt << "\n";
	print(arr);
}




int main()
{
	cin >> n >> m;
	vector arr(n,vector<int>(m,0));
	for (int i=0;i<n;i++)
	{
		for(int j=0;j <m;j++)
		{
			cin >>arr[i][j];
		}
	}
	//모든 지도 돈다.
	map(arr);
}

문제 풀이의 흐름

• 입력 ->

• 변경 맵과 이전 백업맵 2개로 생김

• 이전 백업맵에서 bfs를 하는데 테두리는 다 0이라고 했으니 0,0 부터 쭉 bfs를 하는데

• 4방향 탐색중 1이 있다면 그 부분의 변경맵을 0으로 변경

• 그렇게 쭉 한바퀴를 다 돌고 나면 변경 맵을 검사해서 전부다 0인지 확인

• 전부다 0이면 이전 백업을 출력

• 아니라면 백업을 바꾼 맵으로 바꾸고 다시 함수 시작.

주의 할 점

• 이 문제는 0,0부터 bfs를 한다는 아이디어를 잘 생각해내면 쉬운 문제이다.

반성 및 고찰

오답코드

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

using namespace std;
int n,m;
#define X second
#define Y first
/*
입력 ->
변경 맵과 이전 백업맵 2개로 생김
이전 백업맵에서 bfs를 하는데 4방향 탐색중 0이 있다면 그 부분의
변경맵을 0으로 변경
그렇게 쭉 한바퀴를 다 돌고 나면 변경 맵을 검사해서 전부다 0인지 확인
전부다 0이면 이전 백업을 출력
아니라면 백업을 바꾼 맵으로 바꾸고
다시 함수 시작.
*/

const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};
int check_done(vector<vector<int>> ar)
{
	for (int i=0;i < n;i++)
	{
		for (int j=0; j < m;j++)
		{
			if (ar[i][j] != 0)
				return(1);
		}
	}
	return (0);
}

void	print(vector<vector<int>> ar)
{
	int cnt = 0;
	for(int i=0; i < n; i++)
	{
		for (int j=0;j < m;j++)
		{
			if (ar[i][j] ==1)
				cnt++;
		}
	}
	cout << cnt <<"\n";
}

void	map(vector<vector<int>> &arr)
{
	vector<vector<int>> change = arr;
	queue<pair<int,int>> Q;
	int cnt =0;
	while (check_done(change))
	{
		vector vis(n,vector<int>(m,0));
		arr = change;
		for (int i=0;i <n;i++)
		{
			for (int j=0;j <m;j++)
			{
				if (arr[i][j] ==1 &&  vis[i][j] == 0)
				{
					vis[i][j] = 1;
					Q.push({i,j});
				}
				while (!Q.empty())
				{
					auto it = Q.front();
					Q.pop();
					for (int k=0;k < 4;k++)
					{
						if (it.X +dx[k] < 0 || it.Y + dy[k]<0 ||it.X +dx[k] >=m || it.Y + dy[k] >= n)
						{
							// change[it.Y][it.X] = 0;
							continue;
						}
						if (arr[it.Y + dy[k]][it.X +dx[k]] == 0)
						{
							change[it.Y][it.X] = 0;
							continue;
						}
						if (vis[it.Y + dy[k]][it.X +dx[k]] == 1)
							continue;
						vis[it.Y + dy[k]][it.X +dx[k]]=1;
						Q.push({it.Y+ dy[k], it.X+dx[k]});
					}
				}
			}
		}
		cnt++;
	}
	cout << cnt << "\n";
	print(arr);
}




int main()
{
	cin >> n >> m;
	vector arr(n,vector<int>(m,0));
	for (int i=0;i<n;i++)
	{
		for(int j=0;j <m;j++)
		{
			cin >>arr[i][j];
		}
	}
	//모든 지도 돈다.

	map(arr);


}

사실 중간에 버린 코드이긴 한데 1부터 탐색 하는 것이었다..

이젠 bfs가 확실히 좀 익숙해 졌는지 빠르게 풀려서 기분이 좋았다.

또 함수로 쪼개서 풀고 생각을 정리하면서 푸니까 확실히 알고리즘을 푸는데 도움이 되었다.

Uploaded by N2T