문제
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.
한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 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)가 주어진다. 두 배추의 위치가 같은 경우는 없다.
나의 풀이
이번 문제는 DFS, BFS로 모두 풀이가 가능한 문제였다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Sol {
static int M, N, K;
static boolean[][] graph;
static int[] dx = {1, -1, 0, 0};
static int[] dy = {0, 0, 1, -1};
static int count;
static class Node {
int x;
int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
count = 0;
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
graph = new boolean[M + 2][N + 2];
K = Integer.parseInt(st.nextToken());
for (int j = 1; j <= K; j++) {
st = new StringTokenizer(br.readLine());
**int p1 = Integer.parseInt(st.nextToken()) + 1;**
**int p2 = Integer.parseInt(st.nextToken()) + 1;**
graph[p1][p2] = true;
}
for (int x = 1; x <= N; x++) {
for (int y = 1; y <= N; y++) {
if (graph[y][x]) {
// dfs(x, y);
bfs(x, y);
count++;
}
}
}
System.out.println(count);
}
}
public static void dfs(int x, int y) {
graph[y][x] = false;
for (int i = 0; i < 4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
if (graph[newY][newX]) {
dfs(newX, newY);
}
}
}
public static void bfs(int x, int y) {
graph[y][x] = false;
Queue<Node> que = new LinkedList<>();
Node node = new Node(x, y);
que.add(node);
while (!que.isEmpty()) {
x = que.peek().x;
y = que.peek().y;
graph[y][x] = false;
que.poll();
for (int i = 0; i < 4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
if (graph[newY][newX]) {
que.add(new Node(newX, newY));
}
}
}
}
DFS, BFS 문제를 풀이할 때 visited 배열을 통해 중복체크를 하며 푸는 경우가 많았는데, 이번 풀이에서는 굳이 visited 배열을 이용하지 않고도 graph 배열의 값을 변경해주는 것으로 중복체크를 해낼 수 있었다.
이번 문제 풀이에서 중요한 점이라고 할 수 있는 부분은 바로 graph 배열의 크기 설정이다. 일반적으로 배열의 크기가 주어지면 그에 해당하는 배열을 생성하여 문제를 푸는 것으로 알고 있는데, 주어진 배열보다 좀 더 큰 값으로 배열을 만든다면 그 배열을 감싸는 더 큰 배열을 만들 수 있다.
쉽게 얘기하면 다음과 같은 그림이 된다.
| 1 | 1 | 1 |
| 1 | 1 | 1 |
| 1 | 1 | 1 | 이러한 배열을 감싸면
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
이와 같은 배열을 만들 수 있다는 말인데, 이렇게 해서 얻는 장점이 무엇이냐?
바로 상하좌우 이동의 예외처리를 생략할 수 있다는 부분이다. 즉, 바깥에 감싼 배열들을 다른 값으로 초기화 하지 않는 이상 int[] 인 경우 0, boolean[] 인 경우 false를 기본값으로 기존 배열을 감쌀 수 있다는 것!
이렇게 하기 위해 주어진 배열 값들을 graph 배열에 그대로 담는 것이 아닌 인덱스에 + 1을 한 값을 넣어줌으로써 만들어 낼 수 있다. (위 코드에 강조 표시 해놓았음!)
이제 DFS와 BFS 각각의 코드를 보도록 하자.
DFS
for (int x = 1; x <= N; x++) {
for (int y = 1; y <= N; y++) {
if (graph[y][x]) {
// dfs(x, y);
bfs(x, y);
count++;
}
}
}
------------------------------------------------
public static void dfs(int x, int y) {
graph[y][x] = false;
for (int i = 0; i < 4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
if (graph[newY][newX]) {
dfs(newX, newY);
}
}
}dfs 함수로 값이 들어오면 해당하는 graph 배열의 위치는 false로 바꾸어 준다. 이렇게 하면 visited를 사용할 필요 없이 값의 변경만으로 다음 번의 해당 위치에 들어올 경우의 조건을 만족하지 못하게 할 수 있다. (boolean이 아닌 int 라면 0으로 바꿔준다)
for문을 통한 상하좌우 이동한 값이 graph에서도 참이라면 이 값을 다시 재귀함수를 통해 호출하여 반복수행한다. 탐색위치에서 더 이상 만족하는 값을 찾지 못하면 dfs를 빠져나오고 count++
bfs
for (int x = 1; x <= N; x++) {
for (int y = 1; y <= N; y++) {
if (graph[y][x]) {
// dfs(x, y);
bfs(x, y);
count++;
}
}
}
------------------------------------------------
public static void bfs(int x, int y) {
graph[y][x] = false;
Queue<Node> que = new LinkedList<>();
Node node = new Node(x, y);
que.add(node);
while (!que.isEmpty()) {
x = que.peek().x;
y = que.peek().y;
graph[y][x] = false;
que.poll();
for (int i = 0; i < 4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
if (graph[newY][newX]) {
que.add(new Node(newX, newY));
}
}
}
}bfs는 Queue를 이용하여 구현하기 때문에 dfs와는 코드의 구성이 조금 변하게 된다.
들어온 값에 대한 false 처리를 처음에만 해주면 됐던 dfs와 달리 bfs에서는 반복문 내부에서도 false 처리를 해주어야 한다. 이는 while문의 구조를 보면 이해할 수 있을 것이다.
마찬가지로, 상하좌우 이동을 하면서 해당 좌표의 위치가 참인 경우 이 새로운 값을 Queue에 넣어주고 다음 반복문에서 새로운 값으로 좌표를 만든후 que.poll()하는 과정을 반복한다.
아직 dfs, bfs의 구현과 탈출 조건 등을 머리속에서만 그려내며 코드를 짜는 것이 쉽진 않지만, 이번 문제를 통해서 어느정도 감을 익힐 수 있어서 상당히 도움이 됐다고 생각한다!
