[백준] 1926 그림 Node.js (BFS, DFS 풀이)

Janet·2023년 5월 17일
0

Algorithm

목록 보기
197/314

문제

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

입력

첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)

출력

첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.

예제 입력 1

6 5
1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1

예제 출력 1

4
9

문제풀이

✅ 답안 : BFS - Queue로 풀이

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const paper = require('fs')
  .readFileSync(filePath)
  .toString()
  .trim()
  .split('\n')
  .map((v) => v.split(' ').map(Number));
const [N, M] = paper.shift();
const visited = Array.from(Array(N), () => Array(M).fill(false));
const ds = [[-1, 0], [1, 0], [0, 1], [0, -1]]; // 인접한 네 곳(좌우상하) x,y좌표

// BFS
const bfs = (x, y) => {
  let cnt = 1; // 그림 넓이를 카운트할 변수. 초기값 1로 시작
  const queue = [[x, y]];
  while (queue.length) {
    const [cx, cy] = queue.shift();

	// 현재 위치 기준 인접한 네 곳 탐색할 반복문
    for (let i = 0; i < 4; i++) {
      const nx = cx + ds[i][0];
      const ny = cy + ds[i][1];
		
	  // 종이 밖으로 범위가 벗어나지 않았고, 방문하지 않았으며, 색이 칠해진 부분(value=1)이면
      if (nx >= 0 && nx < N && ny >= 0 && ny < M && !visited[nx][ny] && paper[nx][ny]) {
        visited[nx][ny] = true; // 방문 처리
        cnt++; // 그림 넓이 카운트 증가
        queue.push([nx, ny]); // 현재 위치 큐에 담기
      }
    }
  }
  return cnt; // 그림 넓이 카운트한 값 반환
};

let painting = 0; // 그림 개수 카운팅할 변수
let width = 0; // BFS 실행 후 결과값(현재 넓이) 담을 변수
let maxWidth = 0; // 최고 넓이값 담을 변수
for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
		
	// 방문하지 않았고, 종이에 색이 칠해진 부분(1)이면
    if (!visited[i][j] && paper[i][j]) {
      visited[i][j] = true; // 방문 처리
      painting++; // 그림 개수 카운트 증가
      width = bfs(i, j); // 현재 그림의 넓이는 bfs 실행할 때마다 반환받은 결과값
      if (width > maxWidth) maxWidth = width; // 그림 넓이를 비교하여 큰 값이 최대 넓이가 됨
    }
  }
}

console.log(painting);
console.log(maxWidth);

✅ 답안 #2: DFS - 재귀함수 풀이

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [H, W] = input.shift().split(' ').map(Number);
const graph = input.map((v) => v.split(' ').map(Number));
const dx = [0, 0, -1, 1];
const dy = [1, -1, 0, 0];
const visited = Array.from(Array(H), () => Array(W).fill(false));

let count = 0;
const dfs = (x, y) => {
  count++;
  visited[x][y] = true;

  for (let i = 0; i < 4; i++) {
    const nx = x + dx[i];
    const ny = y + dy[i];

    if (nx >= 0 && nx < H && ny >= 0 && ny < W && !visited[nx][ny] && graph[nx][ny]) {
      dfs(nx, ny);
    }
  }
};

let countArr = [];
for (let i = 0; i < H; i++) {
  for (let j = 0; j < W; j++) {
    count = 0; // 그림 너비 카운트 초기화
    if (!visited[i][j] && graph[i][j]) {
      dfs(i, j);
      countArr.push(count);
    }
  }
}
console.log(countArr.length);
console.log(countArr.length === 0 ? 0 : Math.max(...countArr));
profile
😸

0개의 댓글