[BOJ] 1926: 그림 / JS

문제: https://www.acmicpc.net/problem/1926

 

 

 

 

const [nm, ...input] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

const [n, m] = nm.split(' ').map(Number);
const picture = input.map((s) => s.split(' ').map(Number));

function isRange(x, y) {
  return x >= 0 && x < n && y >= 0 && y < m;
}

const dx = [0, 1, 0, -1];
const dy = [1, 0, -1, 0];

function bfs(i, j) {
  let area = 0;
  picture[i][j] = 0;
  const queue = [[i, j]];
  while (queue.length) {
    let [x, y] = queue.shift();
    area++;
    for (let k = 0; k < 4; k++) {
      const nx = x + dx[k];
      const ny = y + dy[k];
      if (!isRange(nx, ny) || picture[nx][ny] === 0) continue;
      picture[nx][ny] = 0;
      queue.push([nx, ny]);
    }
  }
  return area;
}

let num = 0;
let max = 0;
let area = 0;

function solution() {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (picture[i][j] === 0) continue;
      num++;
      area = bfs(i, j);
      area > max && (max = area);
    }
  }
  console.log(num);
  console.log(max);
}
solution();

"1926: 그림"은 주어진 입력에서 1을 따라가며 그림의 개수와 최대 크기를 구하는 문제다.

그래프를 순회하는 문제이므로 BFS로 풀 수 있다.

 

bfs 함수는 매개변수로 전달받은 시작 지점에서부터 서치를 시작한다.

처음 전달받은 i와 j는 그림의 시작 위치이므로 queue에 넣는다.

이때 해당 위치는 이미 방문했기 때문에 picture[i][j]를 0으로 바꿔야 한다.

picture를 직접 변경하기 싫다면 visit 배열을 만들어서 사용해도 된다.

 

이제부터는 현재 위치에서 상하좌우에 있는 요소들을 검사해야 한다.

picture의 범위를 넘어서거나 이미 방문한 또는 그림이 아닌(값이 0인) 요소들은 무시하고 넘어가야 한다.

 

해당 과정을 처리하기 위해 먼저 queue에서 front를 pop해 현재 위치를 얻는다.

그다음 위, 오른쪽, 아래, 왼쪽 요소를 계산하기 위해 만들어둔 dx, dy 배열의 값을 더해 이웃한 요소에 접근한다.

그리고 범위가 유효한지 방문하지 않은 요소인지 등 유효성 검사를 한다.

만약 유효한 범위 이내고, 아직 방문하지 않은 그림이라면 queue에 push한다.

이때 picture[i][j]에 역시 방문했다는 의미로 0을 할당해야 한다.

위 과정을 거치면 1로 연결된 그림을 순회할 수 있다.

여기서 우리가 구해야 하는 건 그림의 크기(1의 개수)이므로 queue에서 pop할 때마다 area를 1씩 증가시켜야 한다.

 

solution 함수는 그림의 개수와 가장 큰 크기를 구하는 함수다.

따라서 i와 j를 0부터 시작해서 picture를 순회하며 그림의 시작 지점을 찾고, 찾으면 num을 1증가시킨다.

그 후 bfs를 호출해서 area를 구한다.

문제에서 구해야 하는 건 제일 큰 그림의 크기이기 때문에 bfs를 호출한 이후에는 max와 비교해서 더 큰 값으로 업데이트 해야한다.

solution을 실행하면 최종적으로 그림의 개수(num)와 최대 크기(max)를 구할 수 있다.