[SW expert] 1907 모래성 쌓기 삼성 알고르즘 문제

 

1907. 모래성 쌓기

문제 링크

풀이 들어가기전

1000*1000 = n^2 이니깐 완전 탐색은 불가!!!

 

• 1초당 반복문 수행 횟수가 10^8(1억)을 넘으면 시간 초과 가능성.
• O(n^3) : 대략 크기가 2560인 입력까지 1초
• O(n^2) : 40960인 입력 까지 1초
• O(NlogN) : 20000000인 입력 까지 1초
• O(n) : 160000000인 입력 까지 1초

2017/12/30 - [SW/Algorithm] - [알고리즘] Begin Algorithm

[알고리즘] Begin Algorithm

 

대략적인 시간 관련 글은 위에 있습니다.

 

 풀이

 1. N x N을 모두 탐색한다.
2. 만약 ‘.’이라면 8방향을 탐색하고 cnt를 증가시켜 무너트릴 수 있나 확인한다.
3. 무너트릴 수 없다면 다음을 탐색하고 무너트릴 수 있다면 큐에 enqueue 넣는다.
4. 모든 탐색 끝.
5. 큐에서 dequeue 하고 8방향을 탐색하면서 cnt를 증가시킨다.
6. 무너트릴수 있는게 생기면 enqueu.
7. 큐가 비었다면 더이상 무너트릴 수 없으므로 끝.

처음에는 ‘.’이 아닌 숫자의 8방향을 탐색하고 큐에 넣는 큐에서 빼면 그 8 방향의 8방햔을 체크하는 방법을 했는데 시간초과 발생.
‘.’주위를 카운트하고 미리 계산했던건 저장한다면 더욱 중복을 줄일 수 있다.

 

 

코드

/****************************************************************
 *	author	:	jeremy											*
 *	problem :	1907. SandCastle								*
 *	data	:	20/01/08										*
 *****************************************************************/



#include<bits/stdc++.h>
using namespace std;

struct Position{
	int x;
	int y;
	int val;
};

int dx[]={-1, -1,  0,  1, 1, 1, -1, 0};
int dy[]={-1,  0, -1, -1, 1, 0,  1, 1};
int done[1000][1000];
int sand_map[1000][1000];
int count_sand[1000][1000];
queue<Position> q;

int max_x;
int max_y;

void find_weak(int x,int y,int cnt)
{
	Position p;
	int next_x, next_y;
	int current_val=sand_map[x][y];
	if (current_val == -2)
	{
		for(int i=0;i<8;i++)
		{
			next_x=x+dx[i];
			next_y=y+dy[i];

			if(next_x<0 || next_y<0 || next_x>=max_x || next_y>=max_y) // overrange
				continue;
			else{
				if(sand_map[next_x][next_y] > -2){
					count_sand[next_x][next_y]++;
					if (count_sand[next_x][next_y]>=sand_map[next_x][next_y] && done[next_x][next_y]!=1)
					{
						p.x=next_x;
						p.y=next_y;
						p.val=cnt+1;
						q.push(p);
						done[next_x][next_y]=1;
					}
				}
			}
		}
	}
	return ;
}

int main()
{
	int tc;
	cin>>tc;
	for(int num=1;num<=tc;num++)
	{
		//input
		int result=0;
		cin >> max_x;
		cin >> max_y;
		Position c_p={0,0,0};

		for(int x=0;x<max_x;x++)
		{
			string s;
			cin >> s;
			for(int y=0;y<max_y;y++)
			{
				sand_map[x][y]=s[y]-'1'+1;
			}
		}

		//search able delete
		for(int x=0;x<max_x;x++)
		{
			for(int y=0;y<max_y;y++)
			{
				find_weak(x,y,0);
			}
		}
		
		//queue check
		while(!q.empty()){
			
			c_p=q.front();
			q.pop();
			int x=c_p.x;
			int y=c_p.y;
			int cnt=c_p.val;
			sand_map[x][y]=-2;

			//debug
			// cout<<"cnt:"<<cnt<<"/Qsize:"<<q.size()<<"============================="<<endl;
			// cout<<x<<"/"<<y<<endl;
			// for(int x_v=0;x_v<max_x;x_v++)
			// {
			// 	for(int y_v=0;y_v<max_y;y_v++)
			// 	{
			// 		printf("%d\t",sand_map[x_v][y_v]);
			// 	}
			// 	printf("\n");
			// }

			find_weak(x,y,cnt);


			result=cnt;
		}

		cout<<"#"<<num<<" "<<result<<endl;
		//for next tc
		memset(sand_map,0,sizeof(int)*1000*1000);
		memset(count_sand,0,sizeof(int)*1000*1000);
		memset(done,0,sizeof(int)*1000*1000);		
	}
	return 0;
}

 

코드 링크