BOJ[백준] - 1012 - 유기농배추
https://www.acmicpc.net/problem/1012
DFS 또는 BFS로 풀면 될 것 같습니다.
BFS를 쓰면 방문여부만으로도 해결이 되는 문제입니다. 그런걸보면 flood fill 느낌이 나네요..
1. 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 |
#include <stdio.h>
char land[52][52];
int dx[4]={0,1,0,-1}, dy[4]={1,0,-1,0};
void dfs(int x, int y)
{
if (!land[x][y]) return;
land[x][y] = 0;
for (int i=0; i<4; i++)
dfs(x+dx[i], y+dy[i]);
}
int main(void)
{
int T;
scanf("%d",&T);
while (T--)
{
int m,n,k;
scanf("%d %d %d", &m, &n, &k);
while(k--)
{
int x, y;
scanf("%d %d", &x, &y);
land[y+1][x+1] = 1;
}
int Needed = 0;
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
if (land[i][j])
{
dfs(i,j);
Needed++;
}
printf("%d\n", Needed);
}
return 0;
} |
cs |
2. BFS 입니다.
가독성을 위해 아래처럼 코드를 짰지만, 사실 enqueue나 dequeue는 따로 함수로 둘 필요없죠 ㅋ
|
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 |
#include <cstdio>
#define MAX_NUM (52)
typedef struct { int x; int y; } PAIR;
int head, tail, Needed;
int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
PAIR queue[(MAX_NUM * MAX_NUM)];
char land[MAX_NUM][MAX_NUM];
void enqueue(PAIR t)
{
queue[head++] = t;
head = head % MAX_NUM;
}
PAIR dequeue()
{
PAIR t = queue[tail++];
tail = tail % MAX_NUM;
return t;
}
void BFS(PAIR p)
{
int tx, ty;
enqueue(p);
while (head != tail)
{
PAIR p2 = dequeue();
tx = p2.x, ty = p2.y;
for (int i = 0; i<4; i++)
if(land[tx + dx[i]][ty + dy[i]])
land[tx + dx[i]][ty + dy[i]] = 0, enqueue({ tx + dx[i], ty + dy[i] });
}
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
int m, n, k;
scanf("%d %d %d", &m, &n, &k);
while(k--)
{
int x, y;
scanf("%d %d", &x, &y);
land[y+1][x+1] = 1;
}
head = tail = Needed = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (land[i][j])
{
land[i][j] = 0;
BFS({ i, j });
Needed++;
}
}
}
printf("%d\n", Needed);
}
return 0;
} |
cs |
'Algorithm 문제풀이 > BOJ [백준] 문제풀이' 카테고리의 다른 글
| BOJ[백준] - 2262 - 토너먼트 만들기 (0) | 2017.07.30 |
|---|---|
| BOJ[백준] - 13458 - 시험 감독 (0) | 2017.07.18 |
| BOJ[백준] - 1912 - 연속합 (0) | 2017.07.15 |
| BOJ[백준] - 1890 - 점프 (0) | 2017.07.15 |
| BOJ[백준] - 1720 - 타일 코드 (0) | 2017.07.15 |