💛 오늘의 학습 키워드
📝 문제
문제 설명
얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지. 그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!" 정말 도움이 안되는 친구라고 생각했었지. 그런데 막상 또 다시 잠을 청해보려고 침대에 눕고 보니 양을 세고 있더군... 그런데 양을 세다보니 이걸로 프로그램을 하나 짜볼 수 있겠단 생각이 들더군 후후후... 그렇게 나는 침대에서 일어나 컴퓨터 앞으로 향했지.
양을 # 으로 나타내고 . 으로 풀을 표현하는 거야. 서로 다른 # 두 개 이상이 붙어있다면 한 무리의 양들이 있는거지. 그래... 좋았어..! 이걸로 초원에서 풀을 뜯고 있는 양들을 그리드로 표현해 보는거야!
그렇게 나는 양들을 그리드로 표현하고 나니까 갑자기 졸렵기 시작했어. 하지만 난 너무 궁금했지. 내가 표현한 그 그리드 위에 몇 개의 양무리가 있었는지! 그래서 나는 동이 트기 전까지 이 프로그램을 작성하고 장렬히 전사했지. 다음날 내가 잠에서 깨어났을 때 내 모니터에는 몇 개의 양무리가 있었는지 출력되어 있었지.
입력
첫 번째 줄은 테스트 케이스의 수를 나타나는 T를 입력받는다.
이후 각 테스트 케이스의 첫 번째 줄에서는 H,W 를 입력받는다. H는 그리드의 높이이고, W는 그리드의 너비이다. 이후 그리드의 높이 H 에 걸쳐서 W개의 문자로 이루어진 문자열 하나를 입력받는다.
- 0 < T ≤ 100
- 0 < H, W ≤ 100
출력
각 테스트 케이스마다, 양의 몇 개의 무리로 이루어져 있었는지를 한 줄에 출력하면 된다.
입출력 예
Example 입력
2
4 4
#.#.
.#.#
#.##
.#.#
3 5
###.#
..#..
#.###
Example 출력
6
3
💬 내 풀이
import java.io.*;
import java.util.*;
public class Main {
static int h, w;
static char[][] map;
static boolean[][] visit;
static int[] dx = {0, 1, 0, -1}; // 위, 오른쪽, 아래, 왼쪽
static int[] dy = {-1, 0, 1, 0};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
int t = Integer.parseInt(br.readLine()); // 테스트 케이스 개수
int count;
char[] str;
StringTokenizer st;
while (t-- > 0) {
st = new StringTokenizer(br.readLine());
h = Integer.parseInt(st.nextToken()); // 행
w = Integer.parseInt(st.nextToken()); // 열
map = new char[h][w]; // 그리드를 저장하는 배열
visit = new boolean[h][w]; // 확인을 했는지 체크하는 배열
for (int i = 0; i < h; i++) {
str = br.readLine().toCharArray();
for (int j = 0; j < w; j++) {
map[i][j] = str[j];
if (map[i][j] == '.') { // 풀이라면 true로 체크
visit[i][j] = true;
}
}
}
count = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (!visit[i][j]) { // 양이면서 아직 숫자를 세지 않은 양이라면
count++;
function(i, j);
}
}
}
sb.append(count).append("\n");
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
// 하나의 무리를 체크해주는 함수.
private static void function(int y, int x) {
Queue<Integer> yq = new LinkedList<>();
Queue<Integer> xq = new LinkedList<>();
yq.add(y);
xq.add(x);
visit[y][x] = true;
int nowy, nowx, nexty, nextx;
while (!yq.isEmpty()) {
nowy = yq.poll();
nowx = xq.poll();
// 상, 하, 좌우를 검사하기 위한 반복문
for (int i = 0; i < 4; i++) {
nexty = nowy + dy[i];
nextx = nowx + dx[i];
// 그리드를 벗어나지 않으면서 아직 카운터를 세지 않은 양이라면
if (check(nexty, nextx) && !visit[nexty][nextx]) {
visit[nexty][nextx] = true;
// 그 양의 주변도 확인하기 위해 큐에 저장.
yq.add(nexty);
xq.add(nextx);
}
}
}
}
// 그리드 범위 안인지 체크해주는 함수.
private static boolean check(int y, int x) {
return x >= 0 && y >= 0 && x < w && y < h;
}
}