tony9402

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

알고리즘/Baekjoon Online Judge

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

ssu_gongdoli 2018. 8. 16. 01:49
반응형

백준 2667번 단지번호 붙이기






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


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



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

cs



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




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

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


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



1. BFS 이용한 풀이



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#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;
}
cs


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



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#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;
}

cs


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#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;
}

cs


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



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#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;
            }
        }
    }
}

cs


반응형
저작자표시 비영리 동일조건

'알고리즘 > Baekjoon Online Judge' 카테고리의 다른 글

[백준 2178] 미로탐색  (0) 2018.08.21
[백준 2606] 바이러스  (3) 2018.08.17
[백준 10026] 적록색약  (0) 2018.08.16
[백준 1012번] 유기농 배추  (0) 2018.08.16
백준 DFS/BFS 문제  (0) 2018.08.15
'알고리즘/Baekjoon Online Judge' Related Articles more
Comments