# BOJ01012 유기농 배추
https://www.acmicpc.net/problem/1012 (opens new window)
배추들이 모여 있는 곳에 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져 있는지 조사하면 몇 마리의 지렁이가 필요한지 알 수 있다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.
# Location.java
좌표를 관리하기 위한 Location 클래스이다.
private static class Location {
private final int x;
private final int y;
public Location(int x, int y) {
this.x = x;
this.y = y;
}
}
# BFS 활용
모든 배추를 방문하며 기록을 남길 수 있는 bfs 메소드를 선언하였다. 또한 isLocation 메소드를 활용하여 방문 가능한 좌표인지 확인한다.
private static void bfs(int startX, int startY) {
Queue<Location> queue = new LinkedList<>();
queue.add(new Location(startX, startY));
while (!queue.isEmpty()) {
Location location = queue.poll();
for (int i = 0; i < 4; i++) {
int x = location.x + dx[i];
int y = location.y + dy[i];
if (isLocation(x, y)) {
queue.add(new Location(x, y));
visited[x][y] = true;
}
}
}
}
private static boolean isLocation(int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= m || map[x][y] == 0 || visited[x][y]) {
return false;
}
return true;
}
# 제출 코드
우선 선언한 map에 배추의 위치를 체크한다.
map = new int[n][m];
visited = new boolean[n][m];
for (int i = 0; i < k; i++) {
int x = scanner.nextInt();
int y = scanner.nextInt();
map[y][x] = 1;
}
bfs 메소드를 활용하여 방문 가능한 공간을 체크한 후 탐색이 끝나면 count를 증가시킨다.
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (map[i][j] != 0 && !visited[i][j]) {
bfs(i, j);
count++;
}
}
}
아래는 최종 제출 코드이다.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class BOJ1012 {
private static int[][] map;
private static boolean[][] visited;
private static int n, m;
private static final int[] dx = {-1, 0, 1, 0};
private static final int[] dy = {0, 1, 0, -1};
private static class Location {
private final int x;
private final int y;
public Location(int x, int y) {
this.x = x;
this.y = y;
}
}
private static void bfs(int startX, int startY) {
Queue<Location> queue = new LinkedList<>();
queue.add(new Location(startX, startY));
while (!queue.isEmpty()) {
Location location = queue.poll();
for (int i = 0; i < 4; i++) {
int x = location.x + dx[i];
int y = location.y + dy[i];
if (isLocation(x, y)) {
queue.add(new Location(x, y));
visited[x][y] = true;
}
}
}
}
private static boolean isLocation(int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= m || map[x][y] == 0 || visited[x][y]) {
return false;
}
return true;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt(); // 테스트 케이스의 개수
while (t-- > 0) {
m = scanner.nextInt(); // 가로길이
n = scanner.nextInt(); // 세로길이
int k = scanner.nextInt(); // 배추가 심어져 있는 위치의 개수
map = new int[n][m];
visited = new boolean[n][m];
for (int i = 0; i < k; i++) {
int x = scanner.nextInt();
int y = scanner.nextInt();
map[y][x] = 1;
}
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (map[i][j] != 0 && !visited[i][j]) {
bfs(i, j);
count++;
}
}
}
System.out.println(count);
}
}
}
# DFS 활용
모든 배추를 방문하며 기록을 남길 수 있는 dfs 메소드를 선언하였다. 재귀적으로 깊이 탐색하며 방문 체크를 진행한다. 또한 isLocation 메소드를 활용하여 방문 가능한 좌표인지 확인한다.
isLocation 메소드의 경우 이전과 역할은 동일하지만 조금 더 가독성을 높이기 위해 약간의 주석과 줄바꿈을 추가하였다.
private static void dfs(int x, int y) {
if (!isLocation(x, y)) {
return;
}
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
dfs(x + dx[i], y + dy[i]);
}
}
private static boolean isLocation(int x, int y) {
// 공간을 벗어난 경우
if (x < 0 || x >= n || y < 0 || y >= m ) {
return false;
}
// 배추가 아닌 경우
if (map[x][y] == 0) {
return false;
}
// 이미 방문한 경우
if (visited[x][y]) {
return false;
}
return true;
}
# 제출 코드
아래는 최종 제출 코드이다.
import java.util.Scanner;
public class Main {
private static int[][] map;
private static boolean[][] visited;
private static int n, m;
private static void dfs(int x, int y) {
if (!isLocation(x, y)) {
return;
}
visited[x][y] = true;
dfs(x - 1, y);
dfs(x, y - 1);
dfs(x + 1, y);
dfs(x, y + 1);
}
private static boolean isLocation(int x, int y) {
// 공간을 벗어난 경우
if (x < 0 || x >= n || y < 0 || y >= m ) {
return false;
}
// 배추가 아닌 경우
if (map[x][y] == 0) {
return false;
}
// 이미 방문한 경우
if (visited[x][y]) {
return false;
}
return true;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt(); // 테스트 케이스의 개수
while (t-- > 0) {
m = scanner.nextInt(); // 가로길이
n = scanner.nextInt(); // 세로길이
int k = scanner.nextInt(); // 배추가 심어져 있는 위치의 개수
map = new int[n][m];
visited = new boolean[n][m];
for (int i = 0; i < k; i++) {
int x = scanner.nextInt();
int y = scanner.nextInt();
map[y][x] = 1;
}
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (map[i][j] != 0 && !visited[i][j]) {
dfs(i, j);
count++;
}
}
}
System.out.println(count);
}
}
}