유기농 배추
문제
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.
한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
|---|
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 |
입력
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.
출력
각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.
예제 입력 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 2
10 8 17
0 0
1 0
1 1
4 2
4 3
4 5
2 4
3 4
7 4
8 4
9 4
7 5
8 5
9 5
7 6
8 6
9 6
10 10 1
5 5
|
예제 출력 1
예제 입력 2
1
2
3
4
5
6
7
8
| 1
5 3 6
0 2
1 2
2 2
3 2
4 2
4 0
|
예제 출력 2
► Idea
- 인접 행렬을 사용하여 4방향 탐색으로 인접한 노드들을 탐색한다. 각 노드에 대해 4방향 탐색을 통해 배추가 심어져 있으면 탐색을 진행하고, 연결된 노드가 없을 때까지 탐색을 계속한다. 더 이상 노드가 없다면 탐색을 종료한다.
- 지렁이는 상하좌우에 인접한 배추가 있으면 이동할 수 있다. 즉, 인접한 배추들이 있으면 해당 배추들을 따라가며, 더 이상 인접한 배추들이 없을 때까지 하나의 지렁이를 사용할 수 있다.
- DFS와 BFS를 사용할 수 있다.
► Snippets
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
62
63
64
65
66
67
68
69
70
71
72
73
74
| public class Main {
static int n, m;
static int[][] g;
static boolean[][] visited;
static int[] node;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int tc = Integer.parseInt(br.readLine());
for (int t = 1; t <= tc; t++) {
String[] info = br.readLine().split(" ");
m = Integer.parseInt(info[0]);
n = Integer.parseInt(info[1]);
int k = Integer.parseInt(info[2]);
g = new int[51][51];
//노드 저장
node = new int[51];
// 인접 행렬 할당
for (int i = 1; i <= k; i++) {
String[] ab = br.readLine().split(" ");
int x = Integer.parseInt(ab[0]);
int y = Integer.parseInt(ab[1]);
g[x][y] = 1;
}
// 방문 배열 할당
visited = new boolean[51][51];
int result = 0;
//시작할 노드 찾기 (0,0)
// 1이 있으면 dfs Call
for (int i = 0; i < 51; i++) {
for (int j = 0; j < 51; j++) {
if (g[i][j] == 1 && !visited[i][j]) {
dfs(i, j, g, visited);
result++;
}
}
}
System.out.println(result);
}
}
//DFS 동작
private static void dfs(int x, int y, int[][] g, boolean[][] visited) {
//방문 체크
visited[x][y] = true;
// 상하 좌우
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
// 4방 탐색하며 인접 노드 탐색
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx < 0 || ny < 0 || x > g.length || y > g[0].length) {
continue;
}
if (g[nx][ny] == 0) {
continue;
}
// 방문하지 않았고, 노드 있으면 방문체크, dfs recursive call
if (!visited[nx][ny] && g[nx][ny] == 1) {
visited[nx][ny] = true;
dfs(nx, ny, g, visited);
}
}
}
}
|
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
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
| /**
* @Point 왜 그래프 n+2, m+2로 해줘야 하는지
* 큐 BFS 4방탐색
* 예제 2에서 4,0 탐색 안 됨
* 4방탐색 continue 조건 설정
*/
public class Main_BFS {
// 가로 m, 세로 n, 노드 k
static int m, n, k;
static int[][] graph;
static boolean[][] visit;
static int count;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//테케
int tc = Integer.parseInt(br.readLine());
//가로길이, 세로길이, 노드
for (int i = 1; i <= tc; i++) {
String[] info = br.readLine().split(" ");
m = Integer.parseInt(info[0]);
n = Integer.parseInt(info[1]);
k = Integer.parseInt(info[2]);
// 인접 행렬 할당
graph = new int[51][51];
visit = new boolean[51][51];
//인접 행렬 할당 2
for (int j = 1; j <= k; j++) {
String[] ab = br.readLine().split(" ");
int x = Integer.parseInt(ab[0]);
int y = Integer.parseInt(ab[1]);
graph[x][y] = 1;
}
for (int x = 0; x < graph.length; x++) {
for (int y = 0; y < graph[x].length; y++) {
if (graph[x][y] == 1 && !visit[x][y]) {
count++;
bfs(x, y, visit, graph);
}
}
}
System.out.println(count);
count = 0;
}
}
//BFS 시작
private static void bfs(int x, int y, boolean[][] visit, int[][] graph) {
//델타 4방 탐색
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
//큐 배열 선언
Queue<int[]> queue = new LinkedList<>();
//큐에 시작노드 좌표 삽입
queue.add(new int[]{x, y});
//방문 체크
visit[x][y] = true;
//BFS 반복
while (!queue.isEmpty()) {
//좌표배열 있어야 함
int[] current = queue.poll();
int nowX = current[0];
int nowY = current[1];
//4방 탐색 인접 행렬
for (int d = 0; d < 4; d++) {
int nx = nowX + dx[d];
int ny = nowY + dy[d];
if (nx < 0 || ny < 0 || nx >= graph.length || ny >= graph[0].length) {
continue;
}
// 큐에 방문하지 않았고, 4방 탐색 좌표가 1이라면
if (graph[nx][ny] == 1 && !visit[nx][ny]) {
//방문 처리
visit[nx][ny] = true;
queue.add(new int[]{nx, ny});
}
}
}
}
}
|
► 시간 소요한 부분
DFS 호출 시 !visited[i][j] 조건문에 설정해주지 않은 것
1
2
3
4
5
6
7
8
9
10
11
|
for (int i = 0; i < 51; i++) {
for (int j = 0; j < 51; j++) {
if (g[i][j] == 1 && !visited[i][j]) {
dfs(i, j, g, visited);
result++;
}
}
}
System.out.println(result);
|
DFS 메소드 내에서 visit 배열을 체크해주면 된다고 생각해서 Main 메소드 내에서는 visit 배열 체크를 고려하지 않았다.
만약 DFS 메소드 내에서 인접 노드이기에 방문 체크가 되었다면, DFS 종료 이후 다음 시작 노드를 찾을 때 그 노드를 시작으로 DFS를 수행할 수 없다. → 즉, 노드는 1이기에 배추가 심어져 있긴 하나, 인접 노드로서 이미 방문을 했기에 방문할 필요가 없다.
따라서, 한 번 탐색에 사용된 노드가 다른 시작점의 탐색에 영향을 주지 않도록 하기 위해 메인 메소드 내에서도 방문 체크를 해주어야 했다.
BFS 큐 자료구조 할당
1
2
3
4
| //큐 배열 선언
Queue<int[]> queue = new LinkedList<>();
//큐에 시작노드 좌표 삽입
queue.add(new int[]{x, y});
|
- 좌표를 사용해야 했기에 두 개 이상의 값을 한 번에 저장하고 싶었다.
- 예를 들어, 2차원 배열에서의 위치를 나타내는 (x, y)좌표를 저장하고 싶을 때,
Queue<int[]>를 사용하면 int형 배열을 하나의 원소로 저장할 수 있다. new int[]{x, y}- int 타입의 배열을 새로 생성하고, 그 배열에 x와 y라는 두 개의 값을 저장하겠다는 의미다. 왜냐면 큐는 한 번에 하나의 원소만 추가할 수 있는데, x와 y 두 개의 값을 한 번에 큐에 추가하려면 이 두 값을 하나의 단위로 묶어야 했다.
1
2
| // 원래
Queue<int[]> queue = new LinkedList<>();
|
반면, 위는 하나의 정수값 만을 저장한다.
따라서, 저장해야 하는 정보가 하나의 정수일 경우에는 Queue<Integer>를 사용하고, 두 개 이상의 연관된 값을 한 번에 저장하고 싶을 때는 Queue<int[]>를 사용한다.
BFS/DFS 성능 차이
바이러스
1
2
3
4
5
6
7
8
9
| 1
/ \
2 5
\ / \
3 6
/
4
\
7
|
유기농 배추
1
2
3
4
5
6
7
| 0
|
1
|
2 -- 3 -- 4
|
5
|
바이러스 문제의 경우, 트리가 깊고 얕은 경우에 한 레벨을 탐색하고 넘어가므로 DFS처럼 2 →..→ 7 까지 갔다가 재귀호출해서 돌아올 필요가 없었다. 따라서 BFS가 훨씬 빨랐다.
유기농 배추에선 트리가 연결 리스트와 같이 가지가 적다. 이 경우 DFS, BFS 모두 거의 모든 노드 순회해야 하므로 성능 비슷했다.