(H-827 Making A Large Island) 단순 채우기 BFS 재귀 코드

https://leetcode.com/problems/making-a-large-island/

0 : 물

1 : 육지

1개의 0을 1로 바꿀 수 있을 때 ("다리 건설") largest island 크기

 

 

가능한 한 가지 풀이는,

각 섬을 서로 다른 index로 색칠함과 동시에 구한 사이즈를 index로 관리

맨 마지막에 0만 돌면서 주변 island index를 가지고 사이즈 합해서 largest size 찾기

 

즉, BFS flood fill - 단순 색칠 문제

 

 

Queue를 사용하는 긴 BFS 코드 대신, 아래와 같은 재귀 코드를 찾았다.

https://leetcode.com/problems/making-a-large-island/discuss/127015/C%2B%2B-with-picture-O(n*m) 

# OOB 체크
def get(self, x, y):
  boundary_0 = lambda x, y : 0<=x<self.N and 0<=y<self.M
  return 0 if not boundary_0(x, y) else self.grid[x][y] # 0, 1, color
 
def paint(self, x, y, color):
  if self.get(x, y) != 1: # 이미 방문한 경우 (grid > 1; 색칠됨), grid 0 체크
	  return 0
  self.grid[x][y] = color
  return 1 + self.paint(x+1, y, color) + self.paint(x-1, y, color) + self.paint(x, y+1, color) + self.paint(x, y-1, color)

BFS에선 아래 세 가지 경우를 조건문으로 일일히 걸러내야 했다.

1. OOB
2. grid 0
3. 이미 방문한 경우

 

위 풀이에선 깔끔한 설계로 위 세가지 조건을 모두 체크하는 재귀 코드를 짰다. 

get은 1번 조건을 체크한다.

paint는 2/3 조건을 체크하며, 연결된 모든 1을 색칠하면서 구한 사이즈를 리턴한다.

 

 

마지막에 0을 돌면서 주변 island를 합친 사이즈를 조사할 때도, get을 활용.

largest = max(color)
for x in range(self.N):
    for y in range(self.M):
        if grid[x][y] == 0:
            near_islands = set([self.get(x + 1, y), self.get(x - 1, y), self.get(x, y + 1), self.get(x, y - 1)])
            largest = max(largest, 1 + sum(map(lambda x: color[x], near_islands)))
 
return largest

 

결론 :

BFS 최단거리 문제에선 쓰기 힘들어보이지만, 단순 색칠 BFS 문제에서는 쓸만해보인다.

(색칠하고 사이즈 반환)