#2667 단지번호 붙이기

문제는 다음과 같다.(실버1) 연결요소 문제랑 사실상 똑같은 문제이다.

#include <queue>
#include <algorithm>
#include <cstdio>
using namespace std;

int n; //지도의 크기 nxn
int graph[30][30]; //지도
int d[25][25]; //방문했는지 체크
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int sum[25*25]; //각 단지의 집의 개수를 넣을 배열


void bfs(int x,int y,int cnt){
  queue<pair<int,int>> q;
  q.push(make_pair(x,y));
  d[x][y]=cnt;
  while(!q.empty()){
    x=q.front().first; y=q.front().second;
    q.pop();
    for(int i=0;i<4;i++){
      int nx=x+dx[i]; int ny=y+dy[i];
      if(0<=nx&&nx<n && 0<=ny&&ny<n)
        if(graph[nx][ny]==1&&d[nx][ny]==0){
          q.push(make_pair(nx,ny));
          d[nx][ny]=cnt;
        }
    }
  }
}

int main()
{
  scanf("%d",&n); //지도크기 입력
  for(int i=0;i<n;i++){ //지도 입력 구간
    for(int j=0;j<n;j++){
      scanf("%1d",&graph[i][j]);
    }
  }
  int cnt=0;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(graph[i][j]==1&&d[i][j]==0){ //집이있고, 방문한적이 없으면..
        bfs(i,j,++cnt);
      }
    }
  }
  printf("%d\n",cnt);

  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      sum[d[i][j]]++;
    }
  }
  sort(sum+1,sum+cnt+1); 
  for(int k=1;k<=cnt;k++){
    printf("%d\n",sum[k]);
  }
}

코드는 위와 같다. 좀 복잡한데, 좌표정보를 담아서 bfs함수를 돌리다 보니 bfs함수가 많이 복잡해졌다.

 

★ 배운것

- pair 클래스의 사용!

  좌표정보, 키와 밸류를 저장할때 쓸 수 있는 pair를 알게되었다. 선언은 pair<자료형,자료형> 변수명; 이런 식이다.

  알고리즘 카테고리에 따로 정리해뒀음.

- 범위에 신경쓰자!

   bfs함수 내부에 보면 nx의 범위를 if문에 넣어서 처리하고 있는데, 이 코드가 없으면 정답 처리가 되지 않는다. 

   이 뿐만 아니라, 원래는 reset() 함수를 작성해서 d 배열을 전부 0으로 초기화 하는 함수를 썼었는데, 바보같이 0~25       까지 접근하는 바람에 자꾸 런타임 에러가 발생했었다. 이유는 한참뒤에 찾았다... 앞으로는 범위에 좀 더 신경 쓰는 걸로...

- dx,dy배열

  이건 그냥 알게된 스킬(?) 이랄까. 좌표를 이용하는 문제에서 한칸씩 이동할 때 쓰면 유용할것 같다. dx, dy에 값을 하나 씩 넣어두고 for문을 돌리면 쉽게 쓸 수 있다.