Leetcode 200. Number of Islands (Union Find)

https://leetcode.com/problems/number-of-islands/

Number of Islands - LeetCode

 

---

 

이 문제는 Union Find와 관련된 문제로 관련된 개념은 아래에서 참고하실 수 있습니다

 

https://psygo22.tistory.com/59

Union Find

 

---

 

 

처음 짰던 코드는 사방으로 움직였을 때 1이 아니면 새로운 아일랜드를 카운팅 하도록 하는 코드였는데요

unpacking 에서 문제가 계속 발생해서 다른 분들은 어떻게 접근을 했는지 분석해봤습니다! 

 

DFS 방법)

def numIslands(self, grid) :
	if not grid:
    	return 0
        
    count = 0
    for i in range(len(grid)):
    	for j in range(len(grid[0])):
        	if grid[i][j] == '1':
            	self.dfs(grid,i,j)
                count += 1
     return count
     
def dfs(self, grid, i, j):
	if i<0 or j<0 or i >=len(grid) or j > len(grid[0]) or grid[i][j] != 0:
    	return
    grid[i][j] = '#'
    self.dfs(grid,i+1,j)
    self.dfs[grid,i-1,j)
    self.dfs(grid,i,j+1)
    self.dfs(grid,i,j-1)

 

 

이 방법은 아래와 DFS를 활용한 방식은 같지만, VISITED를 만드는 대신,

grid[i][j] = '#'을 넣어서 카운팅에 들어가지 않도록 이미 계산했음을 표시해주는 기발한 방식을 사용한 차이가 있습니다

 

 

def numIslands(self, grid):
	if not grid : return 0
    r,c = len(grid), len(grid[0])
    visited [[False for _ in range(c)] for _ in range(r)]
    
    def dfs(i,j):
    	if i<0 or i>=r or j <0 or j>=c or grid[i][j] == '0' or visited[i][j]:
        	return
        visited[i][j] = True
        dfs(i+1,j)
        dfs(i-1,j)
        dfs(i,j+1)
        dfs(i,j-1) 
    
    count = 0
    for i in range(r):
    	for j in range(c):
        if not visited[i][j] and grid[i][j] == '1':
        	dfs(i,j)
            	count += 1
     return count

 

아래 방식은 1인 항목을 0으로 만들면서 1인 인덱스를 q에 담도록 한 방법입니다

 

from collections import deque
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    #print(i,j,grid)
                    grid[i][j] = '0'
                    self.helper(grid,i,j)
                    count += 1
        return count
    # use a helper function to flip connected '1's to 0
    def helper(self,grid,i,j):
        queue = deque([(i,j)])
        while queue:
            I,J = queue.popleft()
            for i,j in [I+1,J],[I,J+1],[I-1,J],[I,J-1]:
                if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] == '1':
                    #print(i,j, queue)
                    grid[i][j] = '0'
                    queue.append((i,j))

 

BFS 방법)

BFS 방법으로 풀이한 어떤 분의 코드를 가지고 왔는데요

from collections import deque
DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

class Solution:
    def numIslands(self, grid):
        res = 0
        visited = set()
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '0':
                    continue
                if (i, j) in visited:
                    continue
                self.bfs(i, j, grid, visited)
                res += 1
        return res
    
    def bfs(self, x, y, grid, visited):
        queue = deque([(x, y)])
        visited.add((x, y))
        while queue:
            x, y = queue.popleft()
            for dx, dy in DIRECTIONS:
                new_x = x + dx
                new_y = y + dy
                if not (0 <= new_x < len(grid) and 0 <= new_y < len(grid[0])):
                    continue
                if (new_x, new_y) in visited:
                    continue
                if grid[new_x][new_y] == '0':
                    continue
                queue.append((new_x, new_y))
                visited.add((new_x, new_y))

 

확실히 DFS 보다 코드가 길고 복잡한 감이 있네요

 

 

Union Find 방법)

이 방법이 문제의 취지를 가장 잘 살린 코드라고 생각하는데요

이번에 Union Find를 더 확실히 이해하고 넘어가야겠습니다

 

def numIslands(self,grid):
	if len(grid) == 0: return 0
    
    row = len(grid)
    col = len(grid[0])
    
    self.count = sum(grid[i][j] == '1' for i in range(row) for j in range(col))
    parent = [i for i in range(row*col)]
    
    def find(x):
    	if parent[x] != x:
        	return find(parent[x])
        return parent[x]
        
    def union(x,y):
    	xroot, yroot = find(x), find(y)
        if xroot == yroot: return
        parent[xroot] = yroot
        self.count -= 1
        
    for i in range(row):
    	for j in range(col):
        	if grid[i][j] == '0':
            	continue
            index = i*col +j
            if j < col-1 and grid[i][j+1] == '1':
            	union(index,index+1)
            if i < row-1 and grid[i+1][j] == '1':
            	union(index,index+col)
    return self.count

 

 

짧고 명확한 방법)

def numIslands(self, grid):
    def sink(i, j):
        if 0 <= i < len(grid) and 0 <= j < len(grid[i]) and grid[i][j] == '1':
            grid[i][j] = '0'
            list(map(sink, (i+1, i-1, i, i), (j, j, j+1, j-1)))  
            return 1
        return 0
    return sum(sink(i, j) for i in range(len(grid)) for j in range(len(grid[i])))

이 코드는 leetcode에서 정말 놀라운 코드를 많이 게시하시는 StefanPochmann의 코드인데요,, 어떻게 이런 생각을 했는지 감탄하면서 오늘도 배워가네요

 

이 코드에서 map이 이해가 안된다면 아래 게시물을 참고하시면 됩니다!

 

2022.09.27 - [Python] - 파이썬 Map function 다중 변수, 다중 리스트 적용방법

파이썬 Map function 다중 변수, 다중 리스트 적용방법

 

 

---

 

문제를 풀다보면 DFS, BFS, Union Find 등 어떤 방법으로 푸는게 효과적일지 고민하는게 선행되지 못하고

무작정 코드를 쓰려고 하는데요, 코딩을 푸는데에는 여러 방법이 있는만큼 어떤 방법이 가장 효율적인지 고민하면서 접근하는 연습을 계속 해야겠습니다