[BOJ 2468 ] 안전영역

문제 설명

입력

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.

출력

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

풀이

dfs로 풀었는데 사실 bfs로 풀었으면 더 쉬웠을것 같다. 고생한 부분은 "아무 지역도 물에 잠기지 않을 수도 있다." 이부분을 간과하고 높이가 1이상 100이하라는 부분만 참고해서 0인 부분을 체크하지 않고 1부터 나온 높이중 가장 높은부분까지만 체크하는 실수를 했다. 이부분을 체크를 해야했어야했다. 이외에는 dfs에서 재귀를할때 인자들을 맞게 넣었어야 했는데 그러지 않고 좌표만 넣어서 계속 visited에서 undefined가 떴다. 오류라고 에디터에서 좀 느근하게 말해줘서 그냥 js이해가 부족하다 싶었는데 그냥 넣어주질 않아서 그랬다. 잘 체크하자. 근데 코드 자체가 너무 비효율적인것같다. 3중 반복은... 나중에 다시 풀어보자.

소스코드

const fs = require("fs");
const input = fs.readFileSync("./input.txt").toString().trim().split("\n");

const dx = [0, 0, -1, 1];//좌우상하
const dy = [-1, 1, 0, 0];//좌우상하

let N = parseInt(input.shift());
let graph = input.map(it => it.split(" ").map(Number));

let max = -1;
graph.forEach(it => {
    max = Math.max(...it);
})

let cnt = 0;
let result = 0;

const dfs = (graph, visited, x, y, k) => {

    if (x >= N || y >= N || x < 0 || y < 0 || graph[x][y] <= k) return;
    if (visited[x][y] === false) {
        visited[x][y] = true;
        for (let i = 0; i < 4; i++) {
            let nx = x + dx[i];
            let ny = y + dy[i];
            dfs(graph, visited, nx, ny, k);
        }
    }
}


for (let k = 0; k <= max; k++) {
    let visited = Array.from({ length: N }, () => Array(N).fill(false));
    cnt = 0;
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < N; j++) {
            if (graph[i][j] > k && !visited[i][j]) {
                dfs(graph, visited, i, j, k);
                cnt++;
            }
        }
    }
    result = Math.max(result, cnt);
}


console.log(result);

문제링크

https://www.acmicpc.net/problem/2468