현수막

현수막

문제 설명

ANT가 처음 알고리즘 대회를 개최하게 되면서 현수막을 내걸었다.

저번 학기 영상처리 수업을 듣고 배웠던 지식을 최대한 응용 해보고 싶은 혁진이는 이 현수막에서 글자가 몇 개인지 알아보는 프로그램을 만들려 한다.

혁진이는 우선 현수막에서 글자인 부분은 1, 글자가 아닌 부분은 0으로 바꾸는 필터를 적용하여 값을 만드는데 성공했다.

그런데 혁진이는 이 값을 바탕으로 글자인 부분 1이 상, 하, 좌, 우, 대각선으로 인접하여 서로 연결되어 있다면 한 개의 글자라고 생각만 하였다.

혁진이가 필터를 적용하여 만든 값이 입력으로 주어졌을 때, 혁진이의 생각대로 프로그램을 구현하면 글자의 개수가 몇 개인지 출력하여라.

예제 입력

8 19
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 1 1 1 0
0 0 1 0 1 0 0 1 1 0 0 1 0 0 0 1 0 0 0
0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0
0 1 1 1 1 1 0 1 0 1 0 1 0 0 0 1 0 0 0
0 1 0 0 0 1 0 1 0 0 1 1 0 0 0 1 0 0 0
0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

예제 출력

3

---

문제 풀이

const fs = require("fs");
const path = require("path");
const input = fs
  .readFileSync(
    process.platform === "linux"
      ? "dev/stdin"
      : path.join(__dirname, "input.txt")
  )
  .toString()
  .trim()
  .split("\n");
const solution = (input) => {
  let idx = 0;
  const [N, M] = input[idx++].split(" ").map(Number);
  const arr = [];
  for (let i = 0; i < N; i++) {
    arr.push(input[idx++].split(" ").map(Number));
  }
  // 대각선을 고려한 델타 배열 할당
  const dx = [-1, 1, 0, 0, -1, 1, 1, -1];
  const dy = [0, 0, -1, 1, -1, 1, -1, 1];
  // 2차원 방문체크 배열
  const visited = Array.from({ length: N }, () => Array(M).fill(false));

  // dfs 함수
  const dfs = (x, y) => {
    // 현재 값 방문 처리
    visited[x][y] = true;
    let nx = 0;
    let ny = 0;
    // nx, ny 갱신
    for (let k = 0; k < 8; k++) {
      nx = x + dx[k];
      ny = y + dy[k];
      // 범위에 벗어나지 않고 방문하지 않았으며 배열의 원소가 1이라면
      if (
        0 <= nx &&
        nx < N &&
        0 <= ny &&
        ny < M &&
        !visited[nx][ny] &&
        arr[nx][ny] === 1
      ) {
        // 방문체크 후 dfs 수행
        visited[nx][ny] = true;
        dfs(nx, ny);
      }
    }
  };
  let cnt = 0;
  // 배열 원소에 대해 반복
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      // 아직 방문하지 않았고 현재 배열의 원소가 1이라먄 dfs 수행 후 cnt 증가
      if (!visited[i][j] && arr[i][j] === 1) {
        dfs(i, j);
        cnt += 1;
      }
    }
  }
  console.log(cnt);
};
solution(input);

아이디어 / 접근법

1. 델타 + dfs
2. dfs 이후(글자 탐색) 카운트 누적
3. 카운트 반환

후기

이 문제 또한 델타 + dfs를 할 줄 안다면 굉장히 쉬운 문제였음.