[백준 2667번] 단지번호붙이기

백준 2667번 단지번호 붙이기

이 문제는 BFS로 풀어도 되고 DFS로 풀어도 되는 문제이다. 

아는 사람도 있을 것이고 모르는 사람도 있을 수도 있으니 입력부분에서 하나 집고 가자면 예제 입력 부분을 보면 0110100 이런식으로 숫자가 붙어서 들어오는데 scanf를 잘 사용하면 숫자 한개씩 입력 받게 가능하다. (어떤 사람은 이걸 몰라 문자열로 입력 받아 처리하는 경우가 있었다. 이 문제에선 큰 상관이 없긴 하지만 다른 문제에서 쓰일 때가 있을 것이다.)

for(int i=0;i<n;i++)
{
    for(int j=0;j<n;j++)
    {
        scanf("%1d",&map[i][j]);
    }
}

위와 같이 scanf에서 형식 지정자를 %1d로 해주면 정수 1개씩 입력받는다.

이 문제의 풀이를 간략히 설명하자면, 이중 반복문을 돌다가 1인 지점을 찾았을 때부터 주변에 1인 지점을 체크하면서 넓이를 구하면 된다.

이때, visit배열을 만들어 방문했는지 안했는지 체크를 반드시 해줘야한다. 체크를 안해주면 방문했던 곳을 또 다시 방문을 하기 때문이다. 

또는 visit배열을 안만들어도 방문한 지점의 값이 1이면 0으로 바꿔주기만 해도 된다. (단순 넓이만 구하고 면적 개수만 구하면 되기 때문에 입력값이 달라져도 된다.)

1. BFS 이용한 풀이

#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
 
using namespace std;
 
queue<pair<int, int>> q;
vector<int> vc;
 
int map[26][26] = { 0 };
int dx[] = {-1,1,0,0};
int dy[] = {0,0,1,-1};
 
int main()
{
      int n;
 
      scanf("%d",&n);
      for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                  scanf("%1d",&map[i][j]);
      int area;
 
      for(int i=0;i<n;i++)
      {
            for(int j=0;j<n;j++)
            {
                  if(map[i][j] == 1)
                  {
                        area = 0;
                        map[i][j] = 0;
                        q.push(make_pair(i,j));
 
                        while(!q.empty())
                        {
                              area++;
                              pair<int, int> now = q.front();
                              q.pop();
                              for(int k=0;k<4;k++)
                              {
                                    if(now.first + dy[k] < 0 || now.first + dy[k] >= n || now.second + dx[k] < 0 || now.second + dx[k] >= n)continue;
                                    if(map[now.first + dy[k]][now.second + dx[k]] == 1)
                                    {
                                          map[now.first + dy[k]][now.second + dx[k]] = 0;
                                          q.push(make_pair(now.first + dy[k], now.second + dx[k]));
                                    }
                              }
                        }
                        vc.push_back(area);
                  }
            }
      }
 
      printf("%d\n",vc.size());
 
      sort(vc.begin(), vc.end());
 
      for(int i=0;i<vc.size();i++)
      {
            printf("%d\n",vc[i]);
      }
 
      return 0;
}

2. DFS(재귀)를 이용한 풀이

#include<cstdio>
#include<vector>
#include<algoritm>
 
using namespace std;
 
vector<int> vc;
 
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
int n;
int map[26][26];
int room;
 
void dfs(int i, int j)
{
      map[i][j] = 0;
      room++;
      for(int k=0;k<4;k++)
      {
            if(i + dy[k] < 0 || i + dy[k] >= n || j + dx[k] < 0 || j + dx[k] >= n)continue;
            if(map[i + dy[k]][j + dx[k]] == 1)dfs(i + dy[k], j + dx[k]);
      }
}
 
int main()
{
      scanf("%d",&n);
 
      for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                  scanf("%1d",&map[i][j]);
 
      for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                  if(map[i][j] == 1)
                  {
                        room = 0;
                        dfs(i,j);
                        vc.push_back(room);
                  }
 
      sort(vc.begin(), vc.end());
 
      printf("%d\n",vc.size());
 
      for(int i=0;i<vc.size();i++)
      {
            printf("%d\n",vc[i]);
      }
 
      return 0;
}

3. stack(STL)을 이용한 DFS 풀이

#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
 
using namespace std;
 
stack<pair<int, int>> st;
vector<int> vc;
int map[51][51] = { 0 };
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
 
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            scanf("%1d", &map[i][j]);
        }
    }
 
    int room = 0;
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (map[i][j])
            {
                room = 0;
                map[i][j] = 0;
                st.push(make_pair(i, j));
 
                while (!st.empty())
                {
                    room++;
                    pair<int, int> now = st.top(); st.pop();
 
                    for (int k = 0; k < 4; k++) {
                        if (map[now.first + dy[k]][now.second + dx[k]])
                        {
                            map[now.first + dy[k]][now.second + dx[k]] = 0;
                            st.push(make_pair(now.first + dy[k], now.second + dx[k]));
                        }
                    }
                }
                vc.push_back(room);
            }
        }
    }
 
    sort(vc.begin(), vc.end());
 
    printf("%d\n", vc.size());
    for (int i = 0; i < vc.size(); i++)printf("%d\n", vc[i]);
    return 0;
}

C로 Queue 구현해서 짠 소스(STL 쓸 줄 아시면 비추)

#include<stdio.h>
#include<stdlib.h>
 
#define max_queue 50000
 
typedef struct
{
    int x;
    int y;
}pos;
 
typedef struct {
    int size;
    pos *xy;
}queue;
 
void sort(int *result, int n);
 
int main()
{
    int n;
    int *room;
    int *visited;
    int *result;
    int front, back;
    front = back = 0;
    queue *Q;
    scanf("%d", &n);
    room = (int*)malloc(sizeof(int)*n*n);
    visited = (int*)malloc(sizeof(int)*n*n);
    result = (int*)malloc(sizeof(int*)*n*n);
    Q = (queue*)malloc(sizeof(queue));
    Q->size = 0;
    Q->xy = (pos*)malloc(sizeof(pos)*n*n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
        {
            scanf("%1d", &room[i*n + j]);
            visited[i*n + j] = 0;
        }
    }
 
    int qx, qy;
    int roomsize = 0, room_area;
 
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (room[i*n + j] == 1 && visited[i*n+j] == 0)
            {
                visited[i*n + j] = 1;
                Q->size++;
                Q->xy[back].x = j;
                Q->xy[back].y = i;
                back = (back + 1) % max_queue;
                roomsize++;
                room_area = 0;
                while (Q->size!=0)
                {
                    room_area++;
                    Q->size--;
                    qx = Q->xy[front].x;
                    qy = Q->xy[front].y;
                    front = (front + 1) % max_queue;
                    if (qy - 1 >= 0 && room[(qy - 1)*n + qx] == 1 && visited[(qy - 1)*n + qx] == 0)
                    {
                        visited[(qy - 1)*n + qx] = 1;
                        Q->size++;
                        Q->xy[back].x = qx;
                        Q->xy[back].y = qy-1;
                        back = (back + 1) % max_queue;
                    }
                    if (qx - 1 >= 0 && room[(qy)*n + qx-1] == 1 && visited[(qy)*n + qx-1] == 0)
                    {
                        visited[(qy)*n + qx-1] = 1;
                        Q->size++;
                        Q->xy[back].x = qx-1;
                        Q->xy[back].y = qy;
                        back = (back + 1) % max_queue;
                    }
                    if (qy + 1 < n && room[(qy+1)*n + qx] == 1 && visited[(qy +1)*n + qx] == 0)
                    {
                        visited[(qy + 1)*n + qx] = 1;
                        Q->size++;
                        Q->xy[back].x = qx;
                        Q->xy[back].y = qy + 1;
                        back = (back + 1) % max_queue;
                    }
                    if (qx + 1 < n && room[(qy)*n + qx+1] == 1 && visited[(qy)*n + qx+1] == 0)
                    {
                        visited[(qy)*n + qx + 1] = 1;
                        Q->size++;
                        Q->xy[back].x = qx + 1;
                        Q->xy[back].y = qy;
                        back = (back + 1) % max_queue;
                    }
                }
                result[roomsize - 1] = room_area;
            }
        }
    }
 
    printf("%d\n", roomsize);
    sort(result, roomsize);
    for (int i = 0; i < roomsize; i++)
    {
        printf("%d\n", result[i]);
    }
 
    free(Q->xy);
    free(Q);
    free(result);
    free(room);
    free(visited);
    return 0;
}
 
void sort(int *result, int n)
{
    int temp;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (result[i] > result[j])
            {
                temp = result[i];
                result[i] = result[j];
                result[j] = temp;
            }
        }
    }
}