본문 바로가기

Algorithm

1868. 파핑파핑 지뢰찾기

반응형

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc&categoryId=AV5LwsHaD1MDFAXc&categoryType=CODE

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

 

문제에 추가 조건이 있었다. 0일시에 계속 확장 되면서 연달아 터지는 것.

0이 연달아 터지면 해당 경로에 연결된 0들은 당연히 어느지점에서 터지든 동일하게 터지므로 순서 생각 안해줘도됨.

 

 

#include<iostream>
#include<string>
#include<queue>
using namespace std;

string str[300];
int N;

int check(int y, int x)
{
	int count = 0;

	if (y - 1 >= 0)
	{
		if (str[y - 1][x] == '*')
		{
			count++;
		}
	}

	if (y - 1 >= 0 && x - 1 >= 0)
	{
		if (str[y - 1][x - 1] == '*')
		{
			count++;
		}
	}

	if (y - 1 >= 0 && x + 1 < N)
	{
		if (str[y - 1][x + 1] == '*')
		{
			count++;
		}
	}

	if (x - 1 >= 0)
	{
		if (str[y][x - 1] == '*')
		{
			count++;
		}

	}

	if (x + 1 < N)
	{
		if (str[y][x + 1] == '*')
		{
			count++;
		}
	}

	if (y + 1 < N && x - 1 >= 0)
	{
		if (str[y + 1][x - 1] == '*')
		{
			count++;
		}
	}

	if (y + 1 < N)
	{
		if (str[y + 1][x] == '*')
		{
			count++;
		}
	}

	if (y + 1 < N && x + 1 < N)
	{
		if (str[y + 1][x + 1] == '*')
		{
			count++;
		}
	}

	return count;

}

int main(int argc, char** argv)
{
	int test_case;
	int T;

	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{

		cin >> N;

		for (int i = 0; i < N; i++)
		{
			cin >> str[i];
		}

		int result = 0;

		//0인거 먼저 클릭
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (str[i][j] == '.')
				{
					int count = check(i, j);
					if (count == 0)
					{
						result++;
						str[i][j] = '0';

						queue<pair<int, int> > que;
						que.push({ i,j });

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

							if (y - 1 >= 0)
							{
								if (str[y - 1][x] == '.')
								{
									
									
									int count = check(y - 1, x);

									str[y - 1][x] = count  + '0';
									if (count == 0)
									{
										que.push({ y - 1,x });
									}
									
									
								}
							}

							if (y - 1 >= 0 && x - 1 >= 0)
							{
								if (str[y - 1][x - 1] == '.')
								{
									
									
									int count = check(y - 1, x - 1);
									str[y - 1][x - 1] = count + '0';
									if (count == 0)
									{
										que.push({ y - 1,x - 1 });
									}
									
									
									
								}
							}

							if (y - 1 >= 0 && x + 1 < N)
							{
								if (str[y - 1][x + 1] == '.')
								{
									
									
									int count = check(y - 1, x + 1);
									str[y - 1][x + 1] = count + '0';
									if (count == 0)
									{
										que.push({ y - 1,x + 1 });
									}
									
								
								}
							}

							if (x - 1 >= 0)
							{
								if (str[y][x - 1] == '.')
								{
									
									
									int count = check(y, x - 1);
									str[y][x - 1] = count + '0';
									if (count == 0)
									{
										que.push({ y,x - 1 });
									}
									
									
								}

							}

							if (x + 1 < N)
							{
								if (str[y][x + 1] == '.')
								{
									
									
									int count = check(y, x + 1);
									str[y][x + 1] = count + '0';
									if (count == 0)
									{
										que.push({ y,x + 1 });
									}
									
									
								}

							}

							if (y + 1 < N && x - 1 >= 0)
							{
								if (str[y + 1][x - 1] == '.')
								{
									
								
									int count = check(y + 1, x - 1);
									str[y + 1][x - 1] = count + '0';
									if (count == 0)
									{
										que.push({ y + 1,x - 1 });
									}
								
									
								}
							}

							if (y + 1 < N)
							{
								if (str[y + 1][x] == '.')
								{
									
									
									int count = check(y + 1, x);

									str[y + 1][x] = count + '0';
									if (count == 0)
									{
										que.push({ y + 1,x });
									}
									
								}
							}

							if (y + 1 < N && x + 1 < N)
							{
								if (str[y + 1][x + 1] == '.')
								{
									
									
									int count = check(y + 1, x + 1);
									str[y + 1][x + 1] = count + '0';
									if (count == 0)
									{
										que.push({ y + 1,x + 1 });
									}
									
								}
							}
						}
					}
				}
			}
		}
		
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (str[i][j] == '.')
				{
					result++;
					
					int count = check(i, j);
					str[i][j] = count + '0';

				}
			}
		}


		cout << "#" << test_case << " " << result << endl;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}
반응형