[백준][search] 유기농 배추 /런타임 에러 해결

문제

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

필요 지식

•  DFS,BFS 개념 
• memset(arr, false, sizeof(arr)) : 몇차원 배열이든 상관없이 배열내 모든 요소 false로 할당

해결 방법

유기농 배추 밭을 관리하는 사람 입장에서 생각해보자.

관리인은 배추 밭 "전체를 돌아보며" 배추가 있는 자리에 대해 알려고 한다. 

관리인은 움직이며 자신이 간 곳인지 체크하는 자신만의 지도를 가지고 다닌다.

한 칸씩 움직이다가 배추 하나를 찾게 된다면, 그와 인접해 있는 모든 배추를 찾아야 한다.

"상하좌우"로 움직이며 배추를 찾으면 또 다음 배추를 상하좌우로 찾고를 반복한다. 이때, 물론 관리인의 지도에 갔다고 체크해야한다.

인접한 것을 다 찾았다면, 다시 제일 처음에 찾았던 배추자리로 돌아와서 그 자리에 지렁이를 놓는다.

이것을 코드로 옮긴다면,

먼저 배추 밭에 대한 정보가 담긴 farm배열과 관리인이 찾아본 곳인지 체크하는 visit배열이 필요하다. 또,지렁이를 얼마나 썼는지 알기 위해 count를 사용한다.

main함수내에서 배추 밭 전체를 돌아다니는 관리인의 코드가 있어야 한다. for문으로 전체 배추 밭을 돌아다니며, 방문한 곳은 visit에 true로 바꿔준다. 만약 배추가 존재한다면, 상하좌우로 움직이며 인접한 배추를 찾아야 하는데, 이는 재귀 dfs로 해결할 수 있다. 재귀 dfs에서는 현재 입력받은 위치에서 상하좌우로 움직여가며, 인접 배추를 찾았다면 또 인접한 배추를 찾기위해 dfs를 호출하면 된다. 이때, 방문했다는 코드도 삽입해야 한다. 마지막으로 들른 곳에 인접한 배추가 없다면, 다시 돌아와서 제일 처음 배추를 찾았던 곳에서 지렁이를 놓으면 된다. 즉, count++하면 된다.

주의할 점

•  런타임 에러
• 이문제에서는 대부분 배열에서 접근할 수 없는 위치를 접근했을 때 일어난다.
• 즉, DFS내에서 상하좌우로 움직일 때, 혹시 배추 밭의 위치를 벗어나지 않았는지 체크해 보자.

코드