[BOJ] 20947 습격받은 도시

https://www.acmicpc.net/problem/20947

20947번: 습격받은 도시

문제

극악무도한 테러리스트 주현이가 도시를 습격했다. 습격받은 도시는 세로 N$N$칸, 가로 N$N$칸으로 이뤄진 격자 모양이며, 각 칸은 빈칸이거나 건물이 존재한다. 주현이는 자신이 만든 수제 폭탄을 건물이 없는 곳에 설치한다. 폭탄은 터질 때 상하좌우 각 방향에 대해 충격파가 퍼져나가는데, 충격파가 닿은 건물은 파괴되어 건물 잔해가 된다. 충격파는 건물 또는 건물 잔해에 닿고 난 뒤 소멸한다.

이번 테러 사건 수사를 맡은 향빈이는 현장을 재구성하는 중이다. 건물 잔해의 위치를 통해 어떤 위치에서 폭탄이 터졌는지 알아내고자 한다. 아무리 생각해도 폭탄의 위치를 알아낼 수 없는 향빈이는 문제 해결의 대가인 당신을 찾아왔다. 습격받은 도시의 정보가 주어졌을 때, 주현이가 설치한 폭탄의 위치를 구해주자.

입력

다음과 같이 입력이 주어진다.

 N

 a1,1a1,2⋯a1,N

a2,1a2,2⋯a2,N

⋮       ⋮   ⋱  ⋮

aN,1aN,2⋯aN,N

출력

 N개의 줄에 도시의 정보를 출력한다. 각 줄은 N개의 문자를 포함하며 i번째 줄 j번째 문자는 도시의 세로 i번째 가로 j번째 칸에 대한 정보이다. 빈칸일 경우 ., 건물일 경우 O, 건물 잔해일 경우 X, 폭탄이 설치된 칸인 경우 B이다. 답이 여러 가지인 경우, 아무거나 출력한다.

제한

•  N은 도시의 크기이다. (1≤N≤2000)
•  ai,j= . 또는 ai,j= O 또는 ai,j= X 
  •  ai,j= . 면, 도시의 세로 i번째 가로 j번째 칸은 빈칸이다.
  •  ai,j= O 면, 도시의 세로 i번째 가로 j번째 칸은 건물이다.
  •  ai,j=X 면, 도시의 세로 i번째 가로 j번째 칸은 건물 잔해이다.
• 항상 답이 존재하는 경우만 주어진다.

---

풀이

이 문제는 폭탄의 갯수에 제한이 없다. 따라서 부서지지 않는 건물의 네 방향을 제외하고는 모두 폭탄을 설치 할 수 있다.

따라서 건물의 위치를 큐에 넣고 pop하면서 네 방향에 폭탄을 설치 할 수 없다고 표시을 한 뒤, map 전체를 돌면서 폭탄을 설치하는 곳에 모두 폭탄을 설치해 주면 된다.

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <climits>

#define SWAP(a, b, type) do { \
    type temp; \
    temp = a;  \
    a = b;     \
    b = temp;  \
} while (0)

#define INF 1000000000
#define endl '\n'
#define ll long long


using namespace std;

int N;
char map_[2000][2000];
int cnt[2000][2000];

//부서지지 않는 건물의 위치를 저장
queue<pair<int,int> > x_pos;

void input() {
    cin>>N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin>>map_[i][j];
            if(map_[i][j]=='O') x_pos.push(make_pair(i,j));
        }
    }
}

void init() {}


void solution() {
    while(!x_pos.empty()){
        int y=x_pos.front().first, x=x_pos.front().second; x_pos.pop();
        
        //아래
        int tmp=y+1;
        while(tmp<N){
            if(map_[tmp][x]=='.'){
                cnt[tmp][x]++;
                tmp++;
            }else{
                break;
            }
        }
        
        //위
        tmp=y-1;
        while(tmp>=0){
            if(map_[tmp][x]=='.'){
                cnt[tmp][x]++;
                tmp--;
            }else{
                break;
            }
        }
        
        //오른쪽
        tmp=x+1;
        while(tmp<N){
            if(map_[y][tmp]=='.'){
                cnt[y][tmp]++;
                tmp++;
            }else{
                break;
            }
        }
        
        //왼쪽
        tmp=x-1;
        while(tmp>=0){
            if(map_[y][tmp]=='.'){
                cnt[y][tmp]++;
                tmp--;
            }else{
                break;
            }
        }
    }
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            //건물에 영향을 주지않고 빈칸이라면 폭탄을 설치해도 된다.
            if(cnt[i][j]==0&&map_[i][j]=='.') map_[i][j]='B';
        }
    }
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cout<<map_[i][j];
        }
        cout<<endl;
    }
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}