BOJ 1012 : 유기농 배추 - https://www.acmicpc.net/problem/1012
유기농 배추가 모여있는 묶음(?)의 개수를 카운트하면 된다. 이중 for문으로 각 위치를 보며 1인 경우(배추가 있는 경우) BFS로 주변에 붙어있는 배추가 있는지 확인한다. 탐색된 배추들의 값은 -1로 바꿔주어(visited 역할) 다시 for문으로 배추가 있는지 확인할 때 제외되도록 한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static class Loc{
int i;
int j;
public Loc(int i, int j) {
this.i = i;
this.j = j;
}
}
static int[][] map;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int tk = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
while(tk-- > 0) {
String[] inputs = br.readLine().split(" ");
int m = Integer.parseInt(inputs[0]);
int n = Integer.parseInt(inputs[1]);
int k = Integer.parseInt(inputs[2]);
map = new int[n][m];
for (int i = 0; i < k; i++) {
inputs = br.readLine().split(" ");
int x = Integer.parseInt(inputs[0]);
int y = Integer.parseInt(inputs[1]);
map[y][x] = 1;
}
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(map[i][j] == 1){
bfs(i, j, n, m);
cnt++;
}
}
}
sb.append(cnt+"\n");
}
System.out.println(sb);
}
public static void bfs(int i, int j, int n, int m) {
Queue<Loc> q = new LinkedList<>();
q.add(new Loc(i, j));
map[i][j] = -1; // visited
int[] mi = {0, 0, -1, 1};
int[] mj = {1, -1, 0, 0};
while (!q.isEmpty()) {
Loc now = q.poll();
for (int d = 0; d < 4; d++) {
int ni = now.i + mi[d];
int nj = now.j + mj[d];
if(ni<0 || nj<0 || ni>=n || nj>=m) continue;
if(map[ni][nj]==1){
map[ni][nj]=-1;
q.add(new Loc(ni, nj));
}
}
}
}
}
✔ 알고리즘 분류 - 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
✔ 난이도 - ⚪ Silver 2
딱히 없음