[1012번] 유기농 배추 organic cabbage

그래프, dfs, bfs, 211104

문제

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

출력

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

예제 입력 1

Plain Text
복사

예제 출력 1

Plain Text
복사

예제 입력 2

Plain Text
복사

예제 출력 2

Plain Text
복사

My solution

function solution(i) {
    const input = i.toString().trim().split("\n");
    input.shift();
    let M = 0;
    let N = 0;
    let K = 0;
    let field = [...Array(50)].map(() => [...Array(50)].fill(0)); // 1만 찾으면 되므로 50개짜리 0 배열 생성
    const dx = [-1, 0, 1, 0];
    const dy = [0, -1, 0, 1];
    let cnt = 0;
    let res = [];

    function DFS(x, y) {
        field[x][y] = 0;
        for (let i = 0; i < 4; i++) {
            let nx = x + dx[i];
            let ny = y + dy[i];
            if (
                nx >= 0 &&
                ny >= 0 &&
                nx <= M &&
                ny <= N &&
                field[nx][ny] === 1
            ) {
                DFS(nx, ny);
            }
        }
    }

    for (let x of input) {
        let coord = x.split(" ").map((v) => +v);
        if (coord.length > 2) {
            [M, N, K] = coord; // k는 중요하다. k만큼만 좌표들을 할당해놓고 찾기를 시작해야 하기 때문이다.
            continue;
        } // 테스트케이스의 시작, 테케는 마킹을 하므로 연산이 끝나면 field배열은 다시 다 0이 되어 있을 것
        else {
            ++cnt;
            field[coord[0]][coord[1]] = 1;
            if (K === cnt) {
                cnt = 0;
                let answer = 0;
                for (let i = 0; i <= M; i++) {
                    for (let j = 0; j <= N; j++) {
                        if (field[i][j]) {
                            answer++;
                            DFS(i, j);
                        }
                    }
                }
                res.push(answer);
            }
        }
    }
    console.log(res.join("\n"));

    return res.join("\n");
}
JavaScript
복사

DFS로 상하좌우를 방문하는 미로찾기, 섬나라 문제를 풀었기 때문에 이 문제에도 적용해서 테스트케이스를 다 통과하길래 올바른 풀이라고 생각했지만 런타임에러를 만났다.

런타임 에러는 아래와 같은 이유가 있다고 한다.

글 읽기 - 주로 런타임 에러가 발생하는 이유는 무엇인가요?

c++을 시작한지 얼마 되지 않은 학생입니다. 요즘들어서 백준을 풀 떄마다 거의 런타임 에러가 많이 발생하는데 그 이유가 무엇일지 너무 궁금합니다. 주로 런타임 에러가 발생하는 이유는 무엇인가요?

https://www.acmicpc.net/board/view/22980

그래서 재귀 호출이 깊어지는 DFS를 버리고 BFS를 써야된다는 사실을 알았고 아래의 블로그에서도 같은 생각을 해서 BFS로 바꾸어 구현했다고 했다.

https://cider.tistory.com/6

재귀에 대한 이해에 꽂혀서 계속 익숙해지려고 사용하다보니 관련 문제가 나오면 무작정 DFS로 먼저 구현해보는 경우가 있는데 굉장히 자주 스택 호출이 너무 많아지는 에러가 발생한다.

그래서 BFS에 익숙해지는 훈련이 오히려 필요하다는 느낌을 받았다.

const bfs = (시작 정점) => {
    const 방문할 정점 큐 = [시작 정점]; // queue.push(시작정점);
    
    while(방문할 정점 큐에 요소가 없어질 때까지){
        현재 정점=큐에서 첫 번째 요소를 pop;
        
        현재 정점 방문 사실 저장;
        인접한 정점 중 방문하지 않은 정점을 큐에 삽입;
    }
};
JavaScript
복사

생각보다 굉장히 오랜 시간을 고민했는데 2~3시간을 이 한문제에 매달린 것 같다. DFS보다는 BFS 풀이가 훨씬 부족해서 앞으로는 BFS문제, 그래프 문제를 많이 풀어야겠다. 백준에서 입력이 불편하게 주어지는 것도 헷갈린 이유라고 생각한다.

cnt로 들어오는 K가 될 때까지 원소들을 추가해주다가 cnt가 K가 되었을 때 주어진 테스트케이스의 배추를 전부 심은 상태로 생각해서 else문에서 마지막 배추를 심어준 다음에 for문으로 모든 인덱스를 탐색하도록 이중 for문을 만들어주었다.

이중 for문 내에서는 배추가 심어진 공간(1인 공간)을 찾아내서 bfs함수에 넘겨주고 answer를 하나 추가한다.

bfs함수는 그 정점에서 퍼져나가기 때문에 동일한 섬이므로 하나의 answer이기 때문이다.

if (cnt !== K) {
            [n, m] = x.split(" ").map((v) => +v);
            console.log("추가하기 for, n,m", n, m);
            graph[n][m] = 1;
        } else {
            [n, m] = x.split(" ").map((v) => +v);
            console.log("마지막원소 추가 + 확인하기 for, n,m", n, m);
            graph[n][m] = 1;
            for (let a = 0; a < N; a++) {
                for (let b = 0; b < M; b++) {
                    if (graph[a][b] == 1) {
                        bfs(graph, a, b, N, M);
                        answer += 1;
                    }
                }
            }
            result.push(answer);
        }
JavaScript
복사

bfs함수는 그래프(땅의 배열)와 배추가 심어진 정점의 인덱스 a,b, 그리고 그래프의 가로, 세로 n,m이 들어온다.

queue에 해당 정점을 집어넣고 찾은 곳이므로 0을 할당했다.

while문에서는 queue가 비워질 때까지 큐의 원소를 꺼내 for문 내에서 상하좌우를 검사해서 만약 인접한 심어진 배추가 존재한다면 그 정점을 방문해 0으로 바꾼 뒤 큐에 해당 정점을 집어 넣어준다.

const bfs = (graph, a, b, n, m) => {
        queue = [];
        queue.push([a, b]);
        graph[a][b] = 0;

        while (queue.length) {
            [x, y] = queue.shift();
            for (let i = 0; i < 4; i++) {
                let nx = x + dx[i];
                let ny = y + dy[i];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (graph[nx][ny] == 1) {
                    graph[nx][ny] = 0;
                    queue.push([nx, ny]);
                }
            }
        }
        return;
    };
JavaScript
복사

소스코드

function solution(i) {
    const input = i.toString().trim().split("\n");
    input.shift();
    let result = [];
    dx = [0, 0, 1, -1];
    dy = [1, -1, 0, 0];

    const bfs = (graph, a, b, n, m) => {
        queue = [];
        queue.push([a, b]);
        graph[a][b] = 0;

        while (queue.length) {
            [x, y] = queue.shift();
            for (let i = 0; i < 4; i++) {
                let nx = x + dx[i];
                let ny = y + dy[i];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (graph[nx][ny] == 1) {
                    graph[nx][ny] = 0;
                    queue.push([nx, ny]);
                }
            }
        }
        return;
    };

    let graph;
    let cnt;
    for (let x of input) {
        let answer = 0;
        let m, n;
        if (x.split(" ").length === 3) {
            [N, M, K] = x.split(" ").map((v) => +v);
            cnt = 0;
            graph = [...Array(N)].map(() => [...Array(M)].fill(0));
            continue;
        }
        cnt++;
        // console.log("N,M,K", N, M, K, cnt, K, answer);

        if (cnt !== K) {
            [n, m] = x.split(" ").map((v) => +v);
            // console.log("추가하기 for, n,m", n, m);
            graph[n][m] = 1;
        } else {
            [n, m] = x.split(" ").map((v) => +v);
            // console.log("마지막원소 추가 + 확인하기 for, n,m", n, m);
            graph[n][m] = 1;
            for (let a = 0; a < N; a++) {
                for (let b = 0; b < M; b++) {
                    if (graph[a][b] == 1) {
                        bfs(graph, a, b, N, M);
                        answer += 1;
                    }
                }
            }
            result.push(answer);
        }
    }
    console.log(result.join("\n"));

    return result.join("\n");
}

test("solution", () => {
    expect(
        solution(`2
10 8 17
0 0
1 0
1 1
4 2
4 3
4 5
2 4
3 4
7 4
8 4
9 4
7 5
8 5
9 5
7 6
8 6
9 6
10 10 1
5 5`)
    ).toStrictEqual("5\n1");
    expect(
        solution(`1
5 3 6
0 2
1 2
2 2
3 2
4 2
4 0`)
    ).toStrictEqual("2");
});
JavaScript
복사