백준 1012번 : 유기농 배추
이번 문제는 t개의 배추밭이 주어지고 해당 배추밭에 듬성듬성 배추가 심어져 있을 때 상하좌우로 인접한 배추를 지키기 위해 배치되는 배추흰지렁이의 총 마릿수를 구하는 문제이다.
단, 대각선으로 지렁이가 이동하는 경우는 없다.
위 예시에서 0은 배추가 심어지지 않은 땅, 1이 배추가 심어진 땅으로 총 필요한 배추흰지렁이의 마릿수는 5마리이다.
문제에서 지정했듯이 m은 가로길이, n은 세로길이, k는 심어진 배추의 좌표이다.
1
2
3
4
5
6
7
8
public class Main {
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static boolean[][] visited;
static int[][] arr;
static int n, m, k, count = 0;
...
}
각 m,n,k를 포함하여
dx, dy는 이동을 위한 좌표 값
visited는 중복 탐색을 방지하기 위한 방문 여부 배열
arr은 배추밭이다.
또한, count는 배추흰지렁이의 개수이다.
이전에 풀었던 단지번호붙이기에서 조건과 count만 조절해주면 되는데, 조건은 이 문제에서의 그래프가 정사각형이 아닌 것과 그래프가 여러 개 있을 수 있다는 점, count는 탐색을 시작하면 증가해야한다는 점만 조심하면 된다.
우선 주어지는 그래프를 표현하기 위해 메인 함수에서 각 데이터를 입력 받고 반복문을 실행시켜 구현한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
StringTokenizer st;
while (t-- > 0) {
st = new StringTokenizer(br.readLine());
m = Integer.parseInt(st.nextToken());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
arr = new int[n][m];
visited = new boolean[n][m];
for (int i = 0; i < k; i++) {
st = new StringTokenizer(br.readLine());
int y = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
arr[x][y] = 1;
}
...
가장 먼저 입력되는 t는 배추밭의 개수, 즉, 그래프의 개수이다.
t를 가지고 그 만큼 while 반복문을 실행시켰다.
이는 다시 말해, 최종 정답인 count가 여러개가 있을 수 있다는 의미이다.
해당 while문 내부에서 m, n, k를 초기화하고 각 정보를 바탕으로 반복문을 실행시켜 그래프를 생성한다.
다만, 이전 문제들과 달리 이번 그래프는 가로, 세로 크기가 따로 지정되는 직사각형 형태의 그래프이기 때문에 입력되는 특정 위치 arr[x][y]에만 1을 입력하면 된다.
다음으로는 탐색을 시작한다.
1
2
3
4
5
6
7
8
9
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 1 && !visited[i][j]) {
count++;
// bfs(i,j);
dfs(i,j);
}
}
}
배추밭에 심어진 배추로 진입하게 되면 인접한 것이 몇 개든 지렁이는 한 마리만 배치되기 때문에 탐색에 진입하게되면 count를 증가시킨다.
다음으로 탐색인데, 이번에도 마찬가지로 두 가지 탐색 방법을 활용해보았다.
사실 이 두 가지 탐색 법은 단지번호붙이기에서 사용된 탐색과 동일한 방식이고, 해당 포스트에 상세하게 설명이 적혀있다.
그렇기 때문에 여기서는 설명은 따로 적지 않을 것이다.
1. BFS 탐색
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void bfs(int x, int y) {
Queue<int[]> q = new LinkedList<>();
visited[x][y] = true;
q.offer(new int[]{x,y});
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int i = 0; i < 4; i++) {
int nx = cur[0] + dx[i];
int ny = cur[1] + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
if (arr[nx][ny] == 1 && !visited[nx][ny]) {
q.offer(new int[]{nx, ny});
visited[nx][ny] = true;
}
}
}
}
}
앞서말한 이전 문제와 완전히 동일한 탐색법이다.
그런데, 여기서는 각 탐색된 좌표의 개수를 증가시켜 정답을 구하는 문제가 아니기 때문에 이 탐색의 존재 의의는 visited 배열을 활용해 방문 여부를 체크해주는데에 있다.
특별히 달라진 것은 다음 좌표를 탐색하는 조건문이다.
이 조건문에서 현재 그래프가 가로, 세로가 같은 정사각형 형태가 아니기 때문에 각각 다음 x좌표인 nx는 n을 기준으로, 다음 y좌표인 ny는 m을 기준으로 잡혀있는 정도가 다른 점이다.
이외에는 완전히 이전 탐색 알고리즘과 동일하다.
2. DFS 탐색
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void dfs(int x, int y) {
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
if (arr[nx][ny] == 1 && !visited[nx][ny]) {
dfs(nx, ny);
}
}
}
}
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
75
76
77
78
79
80
81
82
83
84
85
86
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static boolean[][] visited;
static int[][] arr;
static int n,m,k,count = 0;
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
StringTokenizer st;
while (t-- > 0) {
st = new StringTokenizer(br.readLine());
m = Integer.parseInt(st.nextToken());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
arr = new int[n][m];
visited = new boolean[n][m];
for (int i = 0; i < k; i++) {
st = new StringTokenizer(br.readLine());
int y = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
arr[x][y] = 1;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 1 && !visited[i][j]) {
count++;
// bfs(i,j);
dfs(i,j);
}
}
}
System.out.println(count);
count = 0;
}
}
public static void bfs(int x, int y) {
Queue<int[]> q = new LinkedList<>();
visited[x][y] = true;
q.offer(new int[]{x,y});
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int i = 0; i < 4; i++) {
int nx = cur[0] + dx[i];
int ny = cur[1] + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
if (arr[nx][ny] == 1 && !visited[nx][ny]) {
q.offer(new int[]{nx, ny});
visited[nx][ny] = true;
}
}
}
}
}
public static void dfs(int x, int y) {
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
if (arr[nx][ny] == 1 && !visited[nx][ny]) {
dfs(nx, ny);
}
}
}
}
}
위에서 아래로 각각 DFS / BFS 결과
이전에는 탐색 알고리즘 구현 자체가 코드가 길어지고 복잡해지는 거 같아 풀기 전부터 지레 겁부터 먹었었는데 막상 집중적으로 풀어보니 결국 알고리즘 자체는 거의 비슷하다.
다만 문제에 대한 조건 설정이나 데이터를 활용하는 것이 다른 것 같다.
실제로 블로그에 풀었던 탐색 문제를 전부 적은 것은 아니지만
실버 3~4 레벨 정도의 문제들은 보통 DFS와 BFS 문제와 크게 다른게 없고
실버 1~2 레벨 정도의 문제들은 단지번호붙이기 문제와 비슷하다.
즉, 탐색 알고리즘의 흐름에 대해 어느정도 이해만 하고 있다면 풀 수 있는 문제들인 것 같다.
물론 내가 비슷한 문제들만 걸린 걸 수도 있다.
어찌되었던 반복숙달이 중요다고 생각한다.