[BOJ 1012] 유기농 배추 C++/Kotlin

 

1012번: 유기농 배추

 

문제풀이

 

배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 

 

 

예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

 

 

1. 배추밭에 대한 정보를 담은 map 배열과 방문 여부를 표시하는 visited 배열을 초기화한다
2. 배추가 심어져 있는 땅을 찾는다
3. DFS를 통해 상하좌우로 인접한 배추가 있는 땅은 모두 방문 표시를 해준다
4. DFS 수행 횟수를 카운트하면 그게 바로 필요한 최소의 배추흰지렁이 마리 수가 된다

 

 

코드

 

C++ 코드

 

 

Kotlin 코드