백준/ Silver 2 문제 , 백준 Node.js 자바스크립트 11123 양 한마리... 양 두마리... [DFS]

백준/ Silver 2 문제 , 백준 Node.js 자바스크립트 11123 양 한마리... 양 두마리... [DFS]

 

 

✔️Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감 🧑‍💻
1. 최상
2. 상
3. 중
4. 하


이해도 🙆‍♂️
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함

 

 

 

문제 출처 🏠

 

https://www.acmicpc.net/problem/11123

11123번: 양 한마리... 양 두마리...

 

 

 

 

문제풀이 소감 🧑‍💻

재밌는 bfs, dfs 문제, 특별한 어려움은 없었고 첫 dfs 호출 카운트만 잘 세주면된다.

 

 

 

요구사항 📋

이어져있지 않은 양의 무리의 개수를 구하시오

 

 

해결 전략 📝

DFS 로 상하좌우를 탐색하면서 이어져 있는 양들을 모두 방문한다. 

 

따로 떨어져 있는 다른 무리의 양이라면 이중 for 문을 돌면서 DFS가 새로 호출 될 것이므로

 

곧, DFS 가 새로 호출될 때마다 새로운 양들의 무리를 찾은 것이다. 그러므로 1씩 카운트 해준다.

 

최종적으로 카운트된 개수가 양들의 무리 개수 이므로 출력한다.

 

 

 

정답 💯

 

 

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const dr_x = [-1, 0, 1, 0];
const dr_y = [0, 1, 0, -1];
const T = Number(input[0]);
let N = 1;

for (let i = 0; i < T; i++) {
  const dfs = (x, y) => {
    for (let k = 0; k < 4; k++) {
      const [mx, my] = [x + dr_x[k], y + dr_y[k]];
      if (mx < 0 || mx >= H || my < 0 || my >= W) continue;
      if (!visited[mx][my] && ground[mx][my] === "#") {
        visited[mx][my] = true;
        dfs(mx, my);
      }
    }
  };

  const [H, W] = input[N].split(" ").map(Number);
  const visited = Array.from(Array(H), () => Array(W).fill(false));
  const ground = [];
  let cnt = 0;
  N += 1;
  for (let j = N; j < N + H; j++) ground.push(input[j].split(""));
  N += H;

  for (let i = 0; i < H; i++) {
    for (let j = 0; j < W; j++) {
      if (ground[i][j] === "#" && !visited[i][j]) {
        cnt += 1;
        dfs(i, j);
      }
    }
  }
  console.log(cnt);
}