[코드트리] 대폭발 C++

문제

https://www.codetree.ai/missions/2/problems/big-explosion?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

계획세우기

4방향으로 모든 폭탄이 퍼져야 하기 때문에 BFS로 풀어도 될 것 같았다(전에 금채굴 문제도 이런 식으로 풀었던 것 같다)

큐에 들어있는 모든 폭탄에 대해 수행해야 하기 때문에 4방향으로 폭탄을 터트린 다음 다시 push해준다!

어차피 처음에 저장해둔 qSize만큼만 반복하기 때문에 다시 넣어줘도 상관 없음

풀이

전에 풀었던 금 채굴 문제를 안 보고 풀었는데, 혼자 힘으로 이제 queue를 쓸 수 있게 된 것 같아서 뿌듯하다....

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

int n, m, r, c;
int arr[101][101];

void PlaceBombs(){
    //좌(0,-1) 상(-1,0) 우(0,1) 하(1,0)
    int dx[4]={0, -1, 0, 1};
    int dy[4]={-1, 0, 1, 0};

    queue <pair<int, int> > bombs;
    bombs.push({r, c}); // 0초에는 (r,c)에만 폭탄이 있음
    arr[r][c]=1;
    
    for(int time=1; time<=m; ++time){
        int size=bombs.size();
        for(int qSize=0; qSize<size; ++qSize){
            int x = bombs.front().first;
            int y = bombs.front().second;
            bombs.pop();

            for(int dir=0; dir<4; ++dir){
                int nx= x+(dx[dir]*pow(2, time-1));
                int ny= y+(dy[dir]*pow(2, time-1));
                // 범위를 벗어나거나 이미 방문했던 곳이라면 continue
                if(nx<0 || nx>=n || ny<0 || ny>=n || arr[nx][ny]==1) continue;
                bombs.push({nx, ny});
                arr[nx][ny]=1;
            }
            bombs.push({x, y});
        }
    }
    
}

int main() {
    cin >> n >> m >> r >>c ;
    r-=1;
    c-=1;
    PlaceBombs();

    int answer=0;
    for(int i=0; i<n; ++i){
        for(int j=0; j<n; ++j){
            if(arr[i][j]==1) answer++;
        }
    }
    cout << answer;
    return 0;
}