[백준] 11123 양 한마리… 양 두마리… Node.js (BFS 풀이)

Janet·2023년 5월 16일
0

Algorithm

목록 보기
195/314

문제

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

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

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

입력

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

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

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

출력

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

예제 입력 1

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

예제 출력 1

6
3

문제풀이

✅ 답안 : BFS - Queue로 풀이

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const tc = Number(input.shift());
const ds = [[-1, 0], [1, 0], [0, 1], [0, -1]]; // 현재 위치 기준 인접한 네 곳(좌우상하 xy좌표
let H, W, graph;

// 양의 무리를 카운트하는 함수
const howManyLambs = () => {
  let answer = 0;
  for (let i = 0; i < H; i++) {
    for (let j = 0; j < W; j++) {
      if (graph[i][j] === '#') {
        answer++;
        bfs(i, j);
      }
    }
  }
  console.log(answer);
};

// BFS
const bfs = (col, row) => {
  const queue = [[col, row]];
  while (queue.length) {
    const [cy, cx] = queue.shift();
		
	// 현재 위치(cy, cx) 기준 인접한 네 곳을 탐색하기 위한 반복문
    for (let i = 0; i < 4; i++) {
      const ny = cy + ds[i][1];
      const nx = cx + ds[i][0];
	
	  // 해당 위치가 범위가 그래프 밖으로 벗어나지 않았고 양이 있는 경우(#)
      if (nx >= 0 && nx < W && ny >= 0 && ny < H && graph[ny][nx] === '#') {
        graph[ny][nx] = '.'; // 방문 처리를 위해 해당 자리 '.'로 변경
        queue.push([ny, nx]); // 해당 위치 큐에 담기
      }
    }
  }
};

// 테스트 케이스가 여러 개인 경우 입력값 정제하기
for (let i = 0; i < input.length - 1; i++) {
  [H, W] = input[i].split(' ').map(Number);
  graph = input.slice(i + 1, i + H + 1).map((v) => v.split(''));
  i += H; // 인덱스에 H만큼 더해서 다음 케이스로 넘어가기
  howManyLambs(); // 양 무리 개수 세는 함수 호출하기
}
profile
😸

0개의 댓글