99클럽 코테 스터디 34일차 TIL 양 한마리... 양 두마리...

# 오늘의 학습 키워드 

깊이/너비 우선 탐색(DFS/BFS)

 

# 오늘의 문제 

문제

얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지.  그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!"  정말 도움이 안되는 친구라고 생각했었지. 그런데 막상 또 다시 잠을 청해보려고 침대에 눕고 보니 양을 세고 있더군... 그런데 양을 세다보니 이걸로 프로그램을 하나 짜볼 수 있겠단 생각이 들더군 후후후... 그렇게 나는 침대에서 일어나 컴퓨터 앞으로 향했지.

양을 # 으로 나타내고 . 으로 풀을 표현하는 거야. 서로 다른 # 두 개 이상이 붙어있다면 한 무리의 양들이 있는거지. 그래... 좋았어..! 이걸로 초원에서 풀을 뜯고 있는 양들을 그리드로 표현해 보는거야!

그렇게 나는 양들을 그리드로 표현하고 나니까 갑자기 졸렵기 시작했어. 하지만 난 너무 궁금했지. 내가 표현한 그 그리드 위에 몇 개의 양무리가 있었는지! 그래서 나는 동이 트기 전까지 이 프로그램을 작성하고 장렬히 전사했지. 다음날 내가 잠에서 깨어났을 때 내 모니터에는 몇 개의 양무리가 있었는지 출력되어 있었지.

입력

첫 번째 줄은 테스트 케이스의 수를 나타나는 T를 입력받는다.

이후 각 테스트 케이스의 첫 번째 줄에서는 H,W 를 입력받는다. H는 그리드의 높이이고, W는 그리드의 너비이다. 이후 그리드의 높이 H 에 걸쳐서 W개의 문자로 이루어진 문자열 하나를 입력받는다. 

• 0 < T ≤ 100
• 0 < H, W ≤ 100

출력

각 테스트 케이스마다, 양의 몇 개의 무리로 이루어져 있었는지를 한 줄에 출력하면 된다. 

 

# 나의 풀이방식 

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);
      }
    }

  }
}