[BFS/DFS] 4방향 탐색

# 2차원 배열 map은 모두 정수 타입 숫자들로 채워져 있다. 여기서 0은 바다를 뜻하고 0 이외의 값은 땅을 뜻한다. map에 몇 개의 섬이 있는지 반환하는 함수를 구현하라.

# map = [ [ 1, 1, 0, 0, 0 ],
#        [ 1, 0, 0, 0, 0 ],
#        [ 0, 0, 0, 1, 0 ],
#        [ 0, 1, 0, 0, 0 ],
#        [ 1, 1, 1, 0, 0 ] ]
        
# the return value should be 3


def search_bfs(i,j,map):
    
    global result
    
    #맨 처음 위치
    q = []
    q.append((i,j))
    check[i][j] = True
    
    while q:
        
        x,y = q.pop(0) #bfs

        
        for k in range(4) : #4방향 이동
            nx, ny = x+dx[k], y+dy[k]
            
            # 경계 체크
            if nx<0 or ny<0 or nx>=n or ny>=m :
                continue

    
            # 땅 체크
            if map[nx][ny] != 0 :
                if not check[nx][ny] : 
                    check[nx][ny] = True
                    q.append((nx,ny))
    
    
    result += 1
    
    return result


def search_dfs(i,j,map):
    
    global result
    
    #처음위치
    s=[]
    s.append((i,j))
    check[i][j] = True
    
    while s:
        
        x,y = s.pop() #dfs

        
        for k in range(4) : #4방향 이동
            nx, ny = x+dx[k], y+dy[k]
            
            # 경계 체크
            if nx<0 or ny<0 or nx>=n or ny>=m :
                continue

    
            # 땅 체크
            if map[nx][ny] != 0 :
                if not check[nx][ny] : 
                    check[nx][ny] = True
                    s.append((nx,ny))
    
    
    result += 1
    
    return result    


def search_dfs_recur(i,j,map):
    
    check[i][j] = True
    global result
    result += 1
    
    for k in range(4):
        nx,ny = i+dx[k], j+dy[k]

        if nx<0 or ny<0 or nx>=n or ny>=m :
            continue
        if map[nx][ny] == 0:
            continue
        
        #재귀호출
        if not check[nx][ny]:
            search_dfs_recur(nx,ny,map)



if __name__ == '__main__':
    map = [ [ 1, 0, 0, 1, 0 ],
           [ 1, 0, 0, 0, 0 ],
           [ 0, 0, 0, 1, 0 ],
           [ 0, 1, 0, 0, 0 ],
           [ 1, 1, 1, 0, 0 ] ]    
    
    
    n = len(map)
    m = len(map[0])
    
    result = 0 #섬의 개수
    ans = []
    
    # 4방향 이동
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    check = [ [False]*(m) for _ in range(n) ]
    
    #출발점
    for i in range(n):
        for j in range(m):
            if not check[i][j] and map[i][j] != 0 : 
                #search_bfs(i,j,map)
                #search_dfs(i,j,map)
                result = 0
                search_dfs_recur(i,j,map)
                ans.append(result)
                
    
    print(result)
    print(ans)