백준 7576번 : 토마토

문제 접근

---

처음에는 아무 생각없이 코드 작성했는데, 지금 보니까 시간 복잡도가 O(N^2*M^2) 인 것 같다 ( 최악의 경우 cnt 가 N*M 이므로). 시간 초과 나오길래 BFS 로 다시 구현했다.

 

BFS 로 구현한 코드는 시간복잡도가 O(V+E) 인 것 같다. ( V : 값이 1인 정점의 개수, E : 값이 1인 정점에서 값이 0인 정점으로 향하는 간선의 개수 )

 

시간 복잡도를 계산하는 것에 조금 더 익숙해질 필요가 있는 것 같다.

 

 

문제 코드 ( 시간 초과 )

---

#include <iostream>
#include <algorithm>

using namespace std;

// cnt = 0의 개수
// 모든 0이 지워져야되는거니 루프마다 0의 개수를 세기보다는 cnt 를 감소하도록 구현했다.
int M,N,cnt=0,ans=0;
int box[1002][1002];
bool visited[1002][1002];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

// 확인용 box 출력 함수
void print()
{
	for(int i=0; i<=N+1; ++i)
	{
		for(int j=0; j<=M+1; ++j)
		{
			cout.fill(' ');
			cout.width(2);
			cout<<box[j][i]<<' ';
		}
		cout<<'\n';
	}

	cout<<"=====================\n";
}

int simulate()
{

	// 0 주변이 모두 -1 이라면 1이 접근할 수 없기에 -1 이 출력되어야 한다.
	for(int i=1; i<=N; ++i)
		for(int j=1; j<=M; ++j)
			if(box[j][i]==0 && box[j+1][i] + box[j][i+1] + box[j-1][i] + box[j][i-1] == -4)
				return -1;
	
    // 0 의 개수가 1개 이상이라면 실행
	while(cnt>0)
	{
    	// 이 코드에서 visited 는 한 번 실행할 때마다 방문 여부 확인하는 것이기에 초기화 함.
		fill(&visited[0][0],&visited[1001][1001],false);
		
		for(int i=1; i<=N; ++i)
			for(int j=1; j<=M; ++j)
            	// 바뀐 1의 좌표를 확인하지 않도록 조건 걸음.
				if(!visited[j][i] && box[j][i]==1)
					for(int k=0; k<4; ++k)
						if(!visited[j+dx[k]][i+dy[k]] && box[j+dx[k]][i+dy[k]]==0)
						{
                        	// BFS 로 한 번 확인할 때 1로 바꾼 부분까지 또 확인해서 바뀐 좌표를 true 로 설정함.
							visited[j+dx[k]][i+dy[k]] = true;
							box[j+dx[k]][i+dy[k]]=1;
							--cnt;
						}
		//print();
		++ans;
	}

	return ans;
}
int main(void)
{
	fill(&box[0][0], &box[1001][1001],-1);
	cin>>M>>N;
	
	for(int i=1; i<=N; ++i)
		for(int j=1; j<=M; ++j)
		{
			cin>>box[j][i];
			if(box[j][i]==0)
				++cnt;
		}

	//print();

	cout<<simulate()<<'\n';
}

 

실행 결과 ( 시간 초과 )

---

구현은 잘 됨.

 

문제 코드 ( 맞았습니다! )

---

#include <iostream>
#include <queue>

using namespace std;

int main(void)
{
	int M,N,cnt=0,ans=0, x, y;
	int box[1002][1002];
	int dx[4] = {0,1,0,-1};
	int dy[4] = {1,0,-1,0};
	
	queue<vector<pair<int,int>>> q;
    // queue 에 넣을 좌표들을 저장한 vector
	vector<pair<int,int>> coor;
	vector<pair<int,int>> temp;
	
	fill(&box[0][0], &box[1001][1001],-1);
	
	cin>>M>>N;
	
	for(int i=1; i<=N; ++i)
		for(int j=1; j<=M; ++j)
		{
			cin>>box[j][i];
			
			if(box[j][i]==0)
				++cnt;
			else if(box[j][i]==1)
				coor.push_back(make_pair(j,i));
		}
	
	q.push(coor);
	
	while(!q.empty())
	{
		coor.clear();
		coor = q.front();
		q.pop();
		
		for(int i=0; i<coor.size(); ++i)
			for(int j=0; j<4; ++j)
			{
				x = coor[i].first;
				y = coor[i].second;
				if(box[x+dx[j]][y+dy[j]]==0)
				{
					box[x+dx[j]][y+dy[j]] = 1;
					temp.push_back(make_pair(x+dx[j], y+dy[j]));
					--cnt;
				}
			}
		
        // temp.empty() 를 확인하지 않으면 빈 vector 가 queue 로 넘어가 무한 루프 걸린다.
		if(!temp.empty())
			q.push(temp);
		temp.clear();
		++ans;
	}
	
    // 바꿀 수 있는 0을 전부 바꿨는데도 0이 남아있으면 모두 익히지 못하는 상황이므로 -1 출력.
	if(cnt)
		cout<<"-1\n";
    
    // ans-1 인 이유는 마지막에 바꿀 수 있는 0을 전부 바꿔서 temp 가 비었을 때도 ++ans 되기 때문이다.
	else
		cout<<ans-1<<'\n';
}