Max area of island

얼마 전에 알고리즘 문제로 섬의 최대 면적을 구하는 문제를 풀었습니다.

 

문제를 설명드리면

 

0과 1로 이루어진 2차원 배열이 있고 0은 바다, 1은 섬을 뜻합니다.

 

섬의 면적은 상하좌우로 연결되어있는 경우만 해당됩니다. (대각선은 포함 X)

 

 

문제 및 예시

 

 

위의 문제를 보면 2차원 배열 안에 섬이 여러 개가 있는데 그중에서 가장 큰 면적을 구하는 문제입니다.

 

 

예시

 

 

예제에서 6이 가장 큰 면적입니다.

 

이 문제를 풀면서 고민이었던 부분은 이미 검색했던 지역을 다시 검색했을 때 어떻게 처리할지 고민이었습니다.

 

그래서 이미 검색한 지역 유무를 체크하기 위해 똑같은 크기의 boolean타입 2차원 배열을 만들어서 풀었습니다.

 

 

소스 코드

 

 

위의 소스 코드를 보게 되면 island라는 바다와 섬으로 이루어진 2차원 배열이 있고 (5라인)

 

그 2차원 배열과 똑같은 크기의 검색 유무 2차원 배열이 선언되어있습니다. (14라인)

 

그리고 아래의 maxAreaOfIsland함수를 통해 섬의 최대 면적을 구하고 있습니다. (16라인)

 

최대 면적을 구하는 방법은 maxAreaOfIsland함수 안에서 각 인덱스 별로 섬의 면적을 검색하고 있습니다.

 

검색할 때 search함수를 재귀로 호출하여 진행하고 있는데 (31라인)

 

인덱스가 배열 범위를 벗어나는 경우, 이전에 검색한 경우, 섬이 아닌 경우에 0을 리턴하여 종료하고 (33, 43, 48라인)

 

아닌 경우 상하좌우로 계속 검색하여 면적을 구하고 있습니다. (40라인)

 

 

컴파일 결과

 

 

해당 소스를 컴파일하여 조회한 결과 예시대로 6이 출력되었습니다.

 

이 문제를 풀 때 재귀 함수 호출하는 조건만 잘 설정하면 쉽게 풀 수 있을 거 같습니다.