#2468 안전영역

문제가 굉장히 길어 캡처가 안된다 ㅎㅎ; URL을 남겨보도록 하겠다.

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

2468번: 안전 영역

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

int n,maxH;
int cnt[101];
int map[101][101];
int visited[101][101];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
queue<pair<int,int>> q;

void bfs(int x,int y,int rain){
  q.push(make_pair(x,y));
  visited[x][y]=1;
  
  while(!q.empty()){
    x=q.front().first; y=q.front().second;
    q.pop();
    for(int k=0;k<4;k++){
      int nx=x+dx[k];
      int ny=y+dy[k];
      if(0<=nx&&0<=ny && nx<n&&ny<n){
        if(map[nx][ny]>rain&&visited[nx][ny]==0){
          q.push(make_pair(nx,ny));
          visited[nx][ny]=1;
        }
      }
    }
  }
}

int main()
{
  freopen("input.txt", "r", stdin);
  int rainH=0;
  cin>>n;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      cin>>map[i][j];
    }
  }

  for(int i=0;i<n;i++){ //최대높이 계산
    for(int j=0;j<n;j++){
      if(maxH<map[i][j])
        maxH=map[i][j];
    }
  }
  while(rainH<=maxH){
    for(int i=0;i<n;i++){ //비가 0왔을때 부터 ~ 최대높이까지 왔을때
      for(int j=0;j<n;j++){
        if(map[i][j]>rainH&&visited[i][j]==0){
          bfs(i,j,rainH);
          cnt[rainH]++;
        }
      }
    }
    rainH++;
    memset(visited,0,sizeof(visited));
  }
  
  
  cout<<*max_element(cnt,cnt+maxH)<<'\n';
}

코드는 위와 같다. 이 문제는 비가 아예오지 않았을때 부터 (rainH 가 0), 최고층의 건물이 잠길때 까지 비가 올때까지 (rainH == maxH) 를 일일히 따져서 bfs의 인자로 넘겼어야하는 문제다. 예전에 푼적 있는 연결요소 문제와 굉장히 흡사하지만 약간 부가적인 조건이 추가되어 시간이 조금 걸렸다.

 

글을 쓰면서 보니까 if(map[i][j]>rainH&&visited[i][j]==0) 이 부분에서의 map[i][j]>rainH 이 코드는 bfs함수 내에서도 확인하고 있다. 하지만 이 코드를 뺀다면, 방문하지 않은 점은 모두 bfs함수를 돌린다. 이렇게 되면 어차피 bfs함수 내에서 걸러질 수 있다 생각할 수 있지만, cnt[rainH]++ 가 여러번 반복되어 원하는 답은 안나온다!

 

★ 배운 것

1. 배열, 벡터 등에서의 최댓값과 최솟값.

배열, 벡터에서의 최대 OR 최소 값은 물론 직접 for문을 돌리면서 구할 수 있지만 쉽게 구할 수 있다. 헤더파일 <algorithm> 안에는 max_element() 와 min_element() 가 있다. 이 함수는 iterator(?) 혹은 주소를 반환하기 때문에 값을 바로 쓰고 싶다면, * (asterisk) 를 사용한다.

- 배열 a

*max_element(a, a+어떤 수);

- 벡터 a

*max_element(a.begin(), a.end());

와 같이 쓸 수 있다.