반응형
▷ 문제 :1012번 : 유기농 배추
▷ 해결 날짜 : 2022.04.06
▷ 소요 시간 : 2시간
▷ 풀이 과정 :
주어지는 값은 테스트 케이스, 배추밭의 가로, 세로의 길이 그리고 배추가 심어져 있는 위치가 주어진다.
문제를 보면 이미지가 첨부되어 있어 쉽게 이해할 수 있도록 도움을 주는데,
결국 인접하고 있는 배추묶음을 하나로 보고 그 묶음의 개수를 세는 것이다. (문제는 배추흰지렁이의 개수를 출력하는 것이지만...)
우선 풀이 순서의 큰 틀을 다음과 같이 정하고 구현하였다.
- 테스트 케이스 만큼 반복
- 각 테스트 케이스 별 그래프(배추밭) 생성
- 배추밭에 배추 삽입
- 전체 탐색하면서 상하좌우 인접배열 탐색
- 개수 출력
- 다음 테스트 케이스 실행
▷ 구현
let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');
// 상 하 좌 우
const ds = [[-1, 0], [1, 0], [0, 1], [0, -1]];
let graph, xMax, yMax, c;
let tc = Number(input.shift());
// 삽입 지렁이 개수 확인
const putWorms = () => {
let result = 0;
for(let i = 0 ; i < yMax ; i++){
for(let j = 0 ; j < xMax ; j++){
if(graph[i][j]) {
bfs(i, j);
result++;
}
}
}
console.log(result);
}
// 반복
const bfs = (startX, startY) => {
const queue = [[startX, startY]];
while(queue.length){
const [x, y] = queue.shift();
if(!graph[x][y]) continue;
else graph[x][y] = 0;
for(let i = 0; i < 4; i++){
const xPos = x + ds[i][0];
const yPos = y + ds[i][1];
if(xPos < 0 || yPos < 0 || xPos >= yMax || yPos >= xMax) continue;
if(graph[xPos][yPos]) queue.push([xPos, yPos]);
}
}
};
for(let i = 0 ; i < tc ; i++){
[xMax, yMax, c] = input.shift().split(' ').map(Number);
// 그래프 생성
graph = [...Array(yMax)].map(e => Array(xMax).fill(0));
// 배추 삽입
for(let j = 0 ; j < c; j++){
let [cx, cy] = input[j].split(' ').map(Number);
graph[cy][cx] = 1;
}
// 배추흰지렁이 개수 확인
putWorms();
// next test case
input = input.slice(c);
}
▷ 복기 :
상당히 오래 걸렸는데, 내가 상하좌우 탐색이 매우 약하다는걸 알게됐다.
이 문제를 기점으로 여러 케이스를 풀어봐야지;
반응형
댓글