문제
어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 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));