백준 1012 - 유기농 배추

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

[1012번: 유기농 배추

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에

www.acmicpc.net](https://www.acmicpc.net/problem/1012)

그래프 탐색을 이용해 connected component의 개수를 찾는 문제이다.

그래프가 하나로 연결되지 않았기 때문에 시작점에서만 BFS나 DFS를 수행하면 답을 찾을 수 없다.

 

해결방법은 2가지가 있다.

1) 내가 생각한 방식으로, 일반적인 그래프 탐색처럼 같은 크기의 visited 배열을 생성해 BFS로 새 위치를 방문할 때마다 이를 기록한다.

2) 그래프의 경로를 찾는 문제가 아니므로, visited 배열 없이 BFS로 새 위치를 방문할 때마다 그 위치의 배추를 삭제한다 (값을 0으로 바꾼다)

둘 중 아래의 방식을 사용해 문제를 해결했으며, 대략적인 코드는 다음과 같다.

for (i = 0; i < row; i++) {  
    for (j = 0; j < col; j++) {  
    {  
        if (arr[i][j]) {
        count++;        //배열의 값이 1이면 새 component 발견

                /* 2번 방식 적용
                새 component를 발견하면 그 위치에서 BFS를 통해 이동하며
                연결된 모든 배추를 제거
                */
                arr[i][j] = 0;    

                Q.push({ i,j });

                //큐의 맨 앞에 저장된 위치로 복귀
                while (!Q.empty()) {
                    cur_pos = Q.front();
                    Q.pop();

                    //해당 위치에서 상하좌우 탐색해 새 길 발견되면 저장 후 이동
                    for (k = 0; k < 4; k++) {
                        next_x = cur_pos.x + dir[k].x;
                        next_y = cur_pos.y + dir[k].y;
                        //배열 범위 체크
                        if (next_x < 0 || next_x >= col || next_y < 0 || next_y >= row) continue;
                        if (arr[next_y][next_x]) {
                            Q.push({ next_y, next_x });
                            arr[next_y][next_x] = 0;
                        }
                    }
                }
            }
        }
    }

이 때 연결된 배추를 제거(arr[i][j] = 0) 하는 시점이 중요하다.

 

* 위 코드에서 front 연산 직후에 배추를 제거하게 되면, 아래의 for문에서 이미 확인한 위치 {next_x, next_y}에 아직 배추가

 

존재하기 때문에 해당 위치는 front로 접근하기 전까지 인접 위치들에 의해 여러 번 큐에 추가된다. 이는 곧 메모리 초과를

 

발생시키게 된다. (경험담) 1번 방식에서 값이 1일 경우 바로 visited를 체크하는 것과 비슷하다고 생각하면 된다.

 

배운 내용 :

- 오랜만에 알고리즘 복습

- memset이 왜 안 되는 걸까

- BFS 구현 방법 : 현재 위치 push하고 시작, 반복문 while empty, 처음에 front

- 작은 크기 배열은 정적으로 생성하기

- X, Y와 행, 열 인덱스를 혼동하지 않게 주의하자