🔗 문제
https://www.acmicpc.net/problem/31863
# 문제 내용
오늘 새벽, 갑자기 규모 5.0 지진이 발생했다. 지진이 발생한 진원지는 N×M 격자 모양의 지역 중 한 곳이다. 진원지에서 발생한 지진을 본진, 건물이 무너졌을 때 발생하는 약한 지진을 여진이라고 하자. 본진은 진원지를 기준으로 상하좌우 각 방향으로 2칸까지 뻗어나가며, 여진은 상하좌우로 1칸까지 뻗어나간다. 본진과 여진은 건물에 영향을 준다. 내진 설계가 되어 있지 않은 건물은 지진이 도달한 즉시 무너지지만, 내진 설계가 되어 있는 건물은 지진이 2번 도달하면 무너진다. 본진과 여진이 뻗어나가는 도중 지진 방파제를 만나거나 격자 모양의 지역 밖으로 나가면 더 이상 뻗어나가지 않는다.
✏️ 풀이
자 문제를 정리해보자.
[변수와 의미]
`char grid[N][M] `
- N, M <= 1000
- @: 진원지
- .: 일반 도로
- *: 내진 설계가 되어있지 않은 건물
- #: 내진 설계가 되어있는 건물
- |: 방파제
[동작]
- 첫 근원지 한 곳(₩@₩)에서 시작되는 본진이 4방을 향해 2칸씩 영향을 주며 시작된다.
- ₩*₩는 1번의 부딪힘으로 건물이 무너진다. -> 다음 여진을 만들어냄
- ₩#₩는 2번의 부딪힘으로 건물이 무너진다. -> 다음 여진을 만들어냄
그렇다면 #에 한번만 부딪혔을 때 *로 바꿔도 같은 효과가 나온다.
문제를 다 풀고 다른 풀이를 보니까 부딪힌 횟수를 따로 저장하는데 굳이 그러지 않아도 되는 풀이를 보여주기 위해 썼다.
[주의할 점]
혹시 예제를 돌렸을 때, 무너진 건물과 무너지지 않은 건물이 뒤바뀌어 나오는 사람들이 있나요?
그렇다면 이 문장을 다시 보자. 건물을 무너뜨렸다고 멈추라는 말이 없다. 건물을 만나도 진동이 전파된다.
본진과 여진이 뻗어나가는 도중 지진 방파제를 만나거나 격자 모양의 지역 밖으로 나가면 더 이상 뻗어나가지 않는다.
💾 소스
#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> pii;
const int MAX_N = 1000 + 1;
const int dx[4] = {0, 1, -1, 0};
const int dy[4] = {1, 0, 0, -1};
int N, M;
bool isValid(const int x, const int y)
{
if(x<0 || y<0 || x>=N || y>=M)
return false;
return true;
}
int main()
{
char grid[MAX_N][MAX_N];
queue<pii> q;
int broken, total;
broken = total = 0;
cin >> N >> M;
for(int i=0; i<N; ++i)
{
for(int j=0; j<M; ++j)
{
cin >> grid[i][j];
if(grid[i][j] == '@')
q.push({i, j});
else if(grid[i][j] == '*' || grid[i][j] == '#')
total++;
}
}
bool start = true;
int range = 2;
while(!q.empty())
{
pii front = q.front(); q.pop();
for (int d = 0; d < 4; ++d)
{
for (int len = 1; len <=range; ++len)
{
int x = front.first + (dx[d] * len);
int y = front.second + (dy[d] * len);
if (!isValid(x, y) || grid[x][y] == '|') break;
if (grid[x][y] == '*')
{
grid[x][y] = '.';
q.push({x, y});
++broken;
continue;
}
if (grid[x][y] == '#')
{
grid[x][y] = '*';
continue;
}
}
}
if(start)
{
start = false;
range = 1;
}
}
cout << broken << " " << total - broken;
return 0;
}