[백준] 11123 양 한마리... 양 두마리... JavaScript

혅·2024년 7월 6일

백준, 프로그래머스 -JavaScript-

목록 보기

114/215

문제

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

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

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

입력

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

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

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

출력

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

예제 입력

2
4 4
#.#.
.#.#
#.##
.#.#
3 5
###.#
..#..
#.###

예제 출력

6
3

내가 했던 풀이 방법

visited 배열을 H×W 크기로 만들고 false로 채워준다.
grassland(입력받은 풀 또는 양) 배열을 순회하면서 해당 요소가 양이고 방문되지 않은 요소일 경우, visited를 true로 바꿔주고, DFS 호출한다. DFS 호출이 끝날 때마다 count를 1 증가시켜준다.
DFS에는 이전 위치를 파라미터로 받는다. prev의 요소를 x, y로 저장해준다. 해당 위치와 연결되어 있으면서 위/아래/왼쪽/오른쪽 방향에 양이 존재하는 경우(양이 붙어있는 경우) 해당 위치의 visited를 true로 바꿔주고, DFS를 호출해준다. 이를 DFS가 끝날 때까지 계속 진행한다.
모든 DFS가 끝난 뒤, count를 출력해준다.

코드

const fs = require('fs');
let [T, ...input] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

T = Number(T);
let index = 0;
for (let k = 0; k < T; k++) {
  let n = input[index++].trim();
  let H = Number(n.split(' ')[0]);
  let W = Number(n.split(' ')[1]);

  let visited = Array.from({ length: H }, () => Array(W).fill(false));
  let grassland = [];
  for (let i = 0; i < H; i++) {
    grassland.push(input[index++].trim().split(''));
  }

  function DFS(prev) {
    let [x, y] = prev;
    if (x !== H - 1 && !visited[x + 1][y] && grassland[x + 1][y] === '#') {
      visited[x + 1][y] = true;
      DFS([x + 1, y]);
    }
    if (x !== 0 && !visited[x - 1][y] && grassland[x - 1][y] === '#') {
      visited[x - 1][y] = true;
      DFS([x - 1, y]);
    }
    if (y !== W - 1 && !visited[x][y + 1] && grassland[x][y + 1] === '#') {
      visited[x][y + 1] = true;
      DFS([x, y + 1]);
    }
    if (y !== 0 && !visited[x][y - 1] && grassland[x][y - 1] === '#') {
      visited[x][y - 1] = true;
      DFS([x, y - 1]);
    }
  }

  let count = 0;
  for (let i = 0; i < H; i++) {
    for (let j = 0; j < W; j++) {
      if (grassland[i][j] === '#' && !visited[i][j]) {
        visited[i][j] = true;
        DFS([i, j]);
        count++;
      }
    }
  }
  console.log(count);
}