[알고리즘 BFS & DFS 17] DAM

문제

---

어느 마을 안에는 큰 호수가 있고, 그것을 막는 댐이 있었다. 그런데 어느날 그 댐이 무너져내려 호수에 있는 물이 마을을 모두 뒤덮으려한다. 호수에 있는 물은 다음 1시간에 한 블럭으로 이동하며, 물의 양은 무한하다 가정하자. 물은 상 하 좌 우로 퍼져나가며 마을을 뒤덮는다.

당신은 댐이 터진 순간 이 마을의 지도를 받았다. 당신이 도와줘야 할 일은 완공시간이 K시간인 댐들을 최대한 빨리 지어서 물이 더 이상 진행하지 못하도록 하는 것이다.

 

입력

---

첫 줄에는 배열의 크기인 T(1 ≤ T ≤100)가 주어지고 다음 줄부터 배열의 값이 주어진다. 0은 텅 빈 길, 1은 건물이다. (물은 건물을 뒤덮지 못한다고 가정한다.) 그리고 그 다음 줄에는 호수의 좌표 x, y(1 ≤ x, y ≤ T) 가 주어지고, 다음 줄에는 댐이 지어지는 시간인 K가 주어진다. 왼쪽 상단의 좌표는 (1, 1)이고, 오른쪽 하단의 좌표는 (T, T)이다. 또한 호수의 좌표에서의 시간은 0이다.

 

출력

---

지어야 하는 댐의 숫자를 출력한다. 만약, 마을이 전부 잠길 때까지 댐을 지을 수 없거나 건물에 둘러쌓여 물이 더이상 진행을 못할 경우엔 "-1"을 출력한다.

 

예제 입력 1

5
0 1 0 0 1
0 0 0 0 0
1 1 1 0 1
0 0 0 0 0
1 0 1 0 1
1 1
5

예제 출력 1

3

예제 입력 2

5
0 0 1 0 0
0 0 0 0 0
1 1 1 0 0
0 0 1 1 0
0 0 0 0 0
5 2
3

예제 출력 2

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#include<iostream>
#include<queue>
using namespace std;
 
const int MAX = 105;
int arr[MAX][MAX];
int check[MAX][MAX];
 
//배열 크기
int t;
//호수의 좌표
int lX, lY;
//댐 완성 시간
int cTime;
 
//좌표 구조체 생성
typedef struct coor{
  int x;
  int y;
  int cnt;
  coor(){};
  coor(int _x, int _y, int _cnt) : x(_x), y(_y), cnt(_cnt){};
}coor;
 
//구조체를 갖는 큐 생성
queue <coor> q;
 
//inside 함수
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
 
bool inside(int x, int y){
  return (x>=0 && x<t) && (y>=0 && y<t);
}
 
 
//호수의 물을 넓힐 BFS
void BFS(){
  if(q.empty()) return;
  
  int x = q.front().x;
  int y = q.front().y;
  int cnt = q.front().cnt;
  q.pop();
  
  
  check[x][y] = 1;
  
  int nx, ny;
  for(int i=0; i<4; i++){
    nx = x + dx[i];
    ny = y + dy[i];
    if(inside(nx,ny) && check[nx][ny]==0){
      check[nx][ny] = 1;
      arr[nx][ny] = cnt;
      q.push(coor(nx,ny,cnt-1));
    }
  }
  
  if(!q.empty()) BFS();
}
 
int main(){
  
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  
  cin >> t;
  
  for(int i=0; i<t; i++){
    for(int j=0; j<t; j++){
      cin >> arr[i][j];
      if(arr[i][j]==1){
        check[i][j]=1;
      }
    }
  }
  
  cin >> lX >> lY;
  cin >> cTime;
  
  q.push(coor(lY-1, lX-1, -1));
  BFS();
  
  int sum = 0;
  for(int i=0; i<t; i++){
    for(int j=0; j<t; j++){
      if(arr[i][j]== -cTime){
        sum++;
      }
    }
  }
  
  if(cTime == 0) cout << -1 << endl;
  else if(sum>0) cout << sum << endl;
  else cout << -1 <<endl;
  
  
  //테스트 출력
  
  /*
  for(int i=0; i<t; i++){
    for(int j=0; j<t; j++){
      cout<<arr[i][j]<<" ";
    }
    cout<<endl;
  }
  */
  
  
  return 0;
}