코딩테스트 문제 (1) - 섬의 개수

이 문제는 페이스북이나 기타 IT 기업에서 면접 때 자주 쓰이는 유명한 문제로 여러 변형들이 있으나 그래프 순회 방법 (DFS)로 푸는 방법은 거의 비슷합니다. 먼저 문제를 살펴 보겠습니다.

문제

다음 그림에서 1을 육지로 0을 물로 가정했을 때, 섬의 개수를 구하여라.

• '1'과 '0'으로 이루어진 중첩 리스트가 입력으로 들어온다고 가정한다.

문제 자체는 위의 그림에서 하얀색 3개의 덩어리를 구하면 되는 문제이고 위 테스트 케이스의 정답은 3이 됩니다. 

풀이

먼저 두 번의 for 루프로 입력으로 들어온 중첩리스트를 훑으면서 '1'을 발견했을 때 어떤 액션을 취해야 할 것 같습니다. 동서남북 방향으로 '1'이 연결되어야 섬의 조건을 만족하므로 (i,j) 점에서 (i+1, j), (i-1, j), (i, j+1), (i, j-1) 점을 탐색해서 그곳이 '1'이라면 다시 동서남북으로 탐색하는 재귀함수를 구성하면 될 것 같습니다.

kaggle.com 의 notebook에서 작성한 풀이는 다음과 같습니다.

 

홍머스 정리

• 주어진 grid가 육지/바다, 아이스크림 기계, 주물 기계 등 다양한 variation 존재
• DFS로 이용한 그래프 탐색으로 풀이 가능
• 난이도: 중 

참조

• <파이썬 알고리즘 인터뷰>, p331-335
• leetcode.com/problems/number-of-islands/