1012번: 유기농 배추
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에
www.acmicpc.net
문제를 단순히 요약하자면 0과 1이 n * m 테이블 형태로 주어졌을 때 1이 모여있는 집단의 개수를 구하라고 요구하고 있다.
그리고 모여있다의 정의는 문제 설명에 나와있다.
첫번째 제출에서는 반례가 나왔고, 두번째 제출에서는 시간 초과가 발생했다. 각각 어떤 이유로 틀렸고 시간초과가 발생했는지 살펴본 뒤 정답 코드를 설명해 보겠다.
틀렸습니다
아래는 처음 제출했던, 반례가 발견된 코드다.
const fs = require("fs");
let input = fs
.readFileSync("/dev/stdin")
.toString()
.trim()
.split("\n")
.map((item) => item.split(" ").map((item) => Number(item)));
const [T] = input.shift();
for (let i = 0; i < T; i++) {
let [M, N, K] = input.shift();
let coordinates = input.splice(0, K);
let field = new Array(N).fill(0).map((item) => new Array(M).fill(0));
let check = new Array(N+1).fill(0).map((item) => new Array(M+1).fill(0));
let cnt = 0;
for (let j = 0; j < coordinates.length; j++) {
let [x, y] = coordinates[j];
field[y][x] = 1;
}
for (let j = 0; j < field.length; j++) {
for (let k = 0; k < field[j].length; k++) {
if (field[j][k] === 1 && !check[j][k]) {
cnt++;
check[j + 1][k] = 1;
check[j][k + 1] = 1;
} else if (field[j][k] === 1 && check[j][k]) {
check[j + 1][k] = 1;
check[j][k + 1] = 1;
}
}
}
console.log(cnt);
}
(x,y) 좌표가 1이라면 (x + 1, y) , (x, y + 1) 좌표를 검사하여 1인 곳에 방문처리를 하여 재방문을 방지한다는 단순한 발상이였다.
하지만 이 방식은 1이 나온 좌표의 오른쪽과 아래만을 검사하기 때문에
1의 위치가 아래 테이블과 같이 존재할 경우, 빨간 원에 해당하는 1은 (0,0) 의 1과 같은 무리임에도 불구하고 방문처리가 되어있지 않아 별개의 무리로 검사되버리고 만다. 이 부분에서 반례가 발생했었다.
시간 초과
위 반례를 통해 다른 방법이 필요하다고 생각했고, 아래 그림과 같이 1이 처음 발견된 좌표에서 연쇄적으로 인접해있는 좌표들을 방문처리를 해야할 것 같다 생각했고, 어떻게 해야 이러한 방문처리를 구현할 수 있을지 고민했다.
위 방법의 "연쇄적인"이란 특성에서 재귀함수를 사용하면 가능할 것 같다는 생각이 들었고,
이 통찰을 통해 아래 코드를 구현할 수 있었다. 하지만 이번엔 시간초과가 발생했다.
const fs = require("fs");
let input = fs
.readFileSync("/dev/stdin")
.toString()
.trim()
.split("\n")
.map((item) => item.split(" ").map((item) => Number(item)));
const [T] = input.shift();
for (let i = 0; i < T; i++) {
let [M, N, K] = input.shift();
let coordinates = input.splice(0, K);
let field = new Array(N + 1).fill(0).map((item) => new Array(M + 1).fill(0));
let check = new Array(N + 1).fill(0).map((item) => new Array(M + 1).fill(0));
const dfs = (j, k) => {
check[j][k] = 1;
let next_j = j + 1;
let next_k = k + 1;
let prev_j = j - 1;
let prev_k = k - 1;
if (field[next_j][k] === 1) {
dfs(next_j, k);
}
if (field[j][next_k] === 1) {
dfs(j, next_k);
}
if (prev_j >= 0 && field[prev_j][k] === 1 && check[prev_j][k] < 1) {
dfs(prev_j, k);
}
if (prev_k >= 0 && field[j][prev_k] === 1 && check[j][prev_k] < 1) {
dfs(j, prev_k);
}
return;
};
let cnt = 0;
for (let j = 0; j < coordinates.length; j++) {
let [x, y] = coordinates[j];
field[y][x] = 1;
}
for (let j = 0; j < field.length; j++) {
for (let k = 0; k < field[j].length; k++) {
if (field[j][k] === 1 && !check[j][k]) {
cnt++;
dfs(j, k);
}
}
}
console.log(cnt);
}
맞았습니다!!
방문 처리를 위한 배열을 따로 생성하여 사용하였던 것이 시간초과의 원인이 되었던 것 같아, 방문 처리를 따로 하지 않고 방문 처리된 1을 0으로 바꾸는 방식으로 개선하였다.
const fs = require("fs");
let input = fs
.readFileSync("/dev/stdin")
.toString()
.trim()
.split("\n")
.map((line) => line.split(" ").map(Number));
const [T] = input.shift();
let answer = "";
// 방향 벡터: 상, 하, 좌, 우
const directions = [
[0, -1], // 상
[0, 1], // 하
[-1, 0], // 좌
[1, 0] // 우
];
for (let i = 0; i < T; i++) {
let [M, N, K] = input.shift();
let coordinates = input.splice(0, K);
let field = Array.from(Array(N), () => Array(M).fill(0));
coordinates.forEach(([x, y]) => {
field[y][x] = 1; // 밭이 있는 곳을 표시
});
const dfs = (x, y) => {
if (x < 0 || x >= M || y < 0 || y >= N || field[y][x] === 0) {
return; // 범위를 벗어나거나, 이미 방문했거나, 밭이 없는 경우
}
field[y][x] = 0; // 방문 표시
directions.forEach(([dx, dy]) => {
const nextX = x + dx;
const nextY = y + dy;
dfs(nextX, nextY);
});
};
let cnt = 0;
for (let y = 0; y < N; y++) {
for (let x = 0; x < M; x++) {
if (field[y][x] === 1) { // 밭이 있고 아직 방문하지 않은 경우
cnt++;
dfs(x, y);
}
}
}
answer += cnt + "\n";
}
console.log(answer);