문제 내용은 입력으로 답을 출력해야 하는 횟수를 받고 이후, 가로 세로 길이를 받고, #와 .으로 이루어진 문자열을 받아서 #갯수가 몇개인지 찾아야 하는데, 동서남북으로 연결된 #는 한개로 치기 때문에 이걸 주의해서 #의 갯수를 출력해줘야 한다
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static char[][] map;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int count = Integer.parseInt(br.readLine());
for (int i = 0; i < count; i++) {
int[] size = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
map = new char[size[0]][size[1]];
for (int j = 0; j < size[0]; j++) {
String s = br.readLine();
for (int k = 0; k < size[1]; k++) {
map[j][k] = s.charAt(k);
}
}
int ans = 0;
boolean[][] visited = new boolean[size[0]][size[1]];
for (int j = 0; j < size[0]; j++) {
for (int k = 0; k < size[1]; k++) {
if (!visited[j][k] && map[j][k] == '#') {
ans++;
dfs(j, k, visited);
}
}
}
System.out.println(ans);
}
}
public static void dfs(int i, int j, boolean[][] visited) {
visited[i][j] = true;
if (i + 1 < map.length) {
if (map[i + 1][j] == '#' && !visited[i + 1][j]) {
dfs(i + 1, j, visited);
}
}
if (i - 1 > -1) {
if (map[i - 1][j] == '#' && !visited[i - 1][j]) {
dfs(i - 1, j, visited);
}
}
if (j + 1 < map[0].length) {
if (map[i][j + 1] == '#' && !visited[i][j + 1]) {
dfs(i, j + 1, visited);
}
}
if (j - 1 > -1) {
if (map[i][j - 1] == '#' && !visited[i][j - 1]) {
dfs(i, j - 1, visited);
}
}
}
}문제를 풀어보자면 for 문을 처음 입력받은 만큼 돌리면서 char[][] map에 입력받은 #와 .로 이루어진 값을 채워넣은 후 전체 배열을 확인하면서 #가 들어있으면서 visited[] 배열이 false인 값을 발견하면 변수에 해당 횟수를 추가해준 뒤 DFS를 돌려주면 되는데
DFS를 돌리면서 상하좌우에 #가 들어있으면 visited[] 배열에 true 처리를 해 줘서 이전 for 문에서 또 방문하는 일이 없도록 하고, 돌리다보면 연결되어 있는 #은 DFS를 돌리면서 모두 제거되기 때문에 여러개나 한개나 모두 1씩만 올라가게 된다
이후 반복문을 모두 돌려준 뒤 #의 갯수를 출력해주면 끝이다
Leave a Reply