백준 2667 단지번호붙이기

문제

1과 0으로 이루어져 있는 정사각형 모양의 지도가 있다. 1은 집이 있는 것을 의미하고 0은 없는 것을 의미한다. 집끼리 연결되어 있는 것을 단지라고 한다. 총 단지의 수를 구하고 각 단지에 포함된 집의 수를 오름차순으로 출력하라.

입력

첫째 줄에 정사각형의 크기 N이 주어지고 그 다음줄부터 정보가 주어진다.

출력

접근

인접한 집을 어떻게 확인할 것인가?
한 번 인집한 집의 탐색을 끝내면 다른 집은 어떻게 탐색할 것인가?

내가 생각한 풀이

전형적인 BFS문제이다. BFS를 통해 인접한 집을 확인한다.
한 번 확인할 때 마다 집의 갯수를 행렬에 저장해준다.
모든 집을 확인하기 위해 for문으로 전체를 확인해준다. 이 때 check가 되어 있는 곳은 제외한다.

코드

#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<cstdio>

using namespace std;
struct xy{
  int x;
  int y;
};
int visited[26][26] = {0, };
int savecount[626] = {0, };
void doBFS(char arr[][26], int visited[][26], queue<struct xy> q, int x_size, int y_size, int count);
int main(void){
  char map[26][26];
  int size, input;
  int count = 0;
  queue<struct xy> q;
  scanf("%d",&size);
  getchar();
  for(int i = 0; i<size;i++){
    for(int j= 0 ; j<size;j++){
      scanf("%c",&map[i][j]);
    }
    getchar();
  }
  for(int i = 0; i<size;i++){
    for(int j= 0 ; j<size;j++){

      if(map[i][j] == 49 && visited[i][j] == 0){
        visited[i][j] = 1;
        struct xy temp;
        temp.x = j;
        temp.y = i;
        q.push(temp);
        count++;
        doBFS(map, visited, q, size, size, count);
        q.pop();
      }
    }
  }
  cout<<count<<"\n";
  sort(savecount,savecount+count);
  for(int i = 0; savecount[i] != 0 ;i++)
    cout<<savecount[i]<<"\n";
  return 0;
}
void doBFS(char arr[][26], int visited[][26], queue<struct xy> q, int x_size, int y_size, int count){
  int apartcount = 0;
  while(q.empty()==0)
  {
    struct xy temp = q.front();
    struct xy temp2;
    visited[temp.y][temp.x] = 1;
    arr[temp.y][temp.x] = count+48;
    if(arr[temp.y][temp.x-1] == 49 && visited[temp.y][temp.x-1] == 0 && temp.x>0){
      temp2.x = temp.x - 1;
      temp2.y = temp.y;
      arr[temp.y][temp.x-1] = count+48;
      visited[temp.y][temp.x-1] = 1;
      q.push(temp2);
    }
    if(arr[temp.y][temp.x+1] == 49 && visited[temp.y][temp.x+1] == 0 && temp.x + 1<x_size){
      temp2.x = temp.x + 1;
      temp2.y = temp.y;
      arr[temp.y][temp.x+1] = count+48;
      visited[temp.y][temp.x+1] = 1;
      q.push(temp2);
    }
    if(arr[temp.y-1][temp.x] == 49 && visited[temp.y-1][temp.x] == 0 && temp.y>0){
      temp2.y = temp.y - 1;
      temp2.x = temp.x;
      arr[temp.y-1][temp.x] = count+48;
      visited[temp.y-1][temp.x] = 1;
      q.push(temp2);
    }
    if(arr[temp.y+1][temp.x] == 49 && visited[temp.y+1][temp.x] == 0 && temp.y + 1<y_size){
      temp2.y = temp.y + 1;
      temp2.x = temp.x;
      arr[temp.y+1][temp.x] = count+48;
      visited[temp.y+1][temp.x] = 1;
      q.push(temp2);
    }
    apartcount++;
    q.pop();
  }
  savecount[count-1] = apartcount;
}

느낀점

알고리즘 공부를 막 시작했을 때 짠 코드이다. 코드도 한 눈에 안 들어오고 쓸데없는 라이브러리를 include시켜놨으며 방향도 하나하나 다 따져놨다… 심지어 0이상 최대값 미만 조건도 하나하나 적어줬다 ㅋㅋㅋ
지금은 방향은 2차원 배열로(4*2로 4방향을 나타냄), 인덱스의 조건은 c(int a, int b){return a>=0 && b<max;} 과 같이 나타낸다. 가독성도 중요하다는 것을 깨닫게 해주는 코드인 것 같다…ㅎ