반응형
문제에 추가 조건이 있었다. 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을 리턴해야합니다.
}
반응형
'Algorithm' 카테고리의 다른 글
1218. [S/W 문제해결 기본] 4일차 - 괄호 짝짓기 (0) | 2020.03.23 |
---|---|
5650. [모의 SW 역량테스트] 핀볼 게임 (0) | 2020.03.22 |
3459. 승자 예측하기 (0) | 2020.03.20 |
2819. 격자판의 숫자 이어 붙이기 (0) | 2020.03.20 |
SW 1824. 혁진이의 프로그램 검증 (0) | 2020.03.19 |