[백준 1012 유기농 배추] 파이썬 BFS 너비 우선 탐색 풀이

유기농 배추 문제

1012번: 유기농 배추

2차원 배열의 유기농 배추밭이 주어지고 0(땅) 과 1(배추 심어져 있는 땅)로 데이터가 구분됩니다. 배추흰 지렁이를 배추에 서식하게 하면 사방면으로 이동이 가능하여 다른 배추를 해충으로부터 보호가 가능하다. 필요한 배추흰 지렁이의 마리수를 구하는 문제입니다. 입력 받는 정보로 아래와 같이 배추 밭을 2차원 배열 형태로 만들어 주어야 합니다.

 

문제 풀이

4방면으로 이동이 가능하므로 각 영역당 한마리의 배추흰 지렁이를 배치하면 해결할 수 있습니다. 즉, 1로되어있는 영역이 몇개있는지 구하는 문제이므로 BFS 너비 우선 탐색을 통해 풀수 있습니다.

 

1. 입력받은 지렁이의 좌표를 2차원 배열에 1로 표시
2. BFS 너비 우선 탐색으로 1의 영역이 몇개 있는지 확인

 

2차원 배열의 높이 H, 너비 W라고 했을때 최선, 최악 모두 시간 복잡도 O(HW)가 됩니다. 방문 정보를 남겨 방문 안한 곳만 순회하여 2차원배열 전체를 딱 한번만 확인하면 됩니다.

 

 

파이썬 코드