[알고리즘] FloodFill(SeedFill) 플러드 필 알고리즘

플러드 필 알고리즘

flood fill 혹은 seed fill이라고 불리는 알고리즘이다.

다차원 배열에서 어떤 칸과 연결된 영역을 찾는 알고리즘이며, 채우기 도구나 지뢰 찾기 게임에서 사용된다.

일반적으로 시작 칸을 중심으로 상하좌우로 연결 된 모든 칸을 방문하여 색을 칠하는 구조이다.

여러가지 구현 방법이 있지만, 큐나 스택의 자료구조를 사용하는 것이 일반적이다.

4방향과 8방향으로 구분되며, 알고리즘 문제에서는 주로 4방향 문제를 주어진다.

(8 방향의 경우, 상하좌우 + 대각선을 탐색한다)

 

플러드필 알고리즘의 사용 예

모든 정점에서 dfs나 bfs 탐색을 통해 연결요소가 몇개인지 파악할 수 있다.

 

구현

 

https://school.programmers.co.kr/learn/courses/30/lessons/154540

프로그래머스

프로그래머스의 무인도 여행 문제를 참고했다.

 

 

위와 같이 무인도 영역이 주어졌을 경우, 각 숫자 영역들을 합한 리스트를 구하는 문제였다.

여행자는 상,하,좌,우 4방향에 대해서 이동할 수 있으며, X는 바다를 나타내기 때문에 탐색할 수 없다는 규칙이 있다.

 

<전체 코드>

def solution(maps):
    answer = []
    visited = [[False] * len(maps[0]) for _ in range(len(maps))]
    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if not visited[i][j] and maps[i][j]!="X":
                answer.append(check(visited,maps,i,j))
    if len(answer)==0: return [-1]
    return sorted(answer)

def check(visited,maps,i,j):
    visited[i][j] = True
    sum_data = int(maps[i][j])
    for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
        x,y = i+dx,j+dy
        if 0 <= x < len(maps) and 0 <= y < len(maps[0]) and maps[x][y]!="X" and not visited[x][y]:
            sum_data+=check(visited,maps,x,y)
    return sum_data


print(solution(["X591X","X1X5X","X231X", "1XXX1"]))

 

우선 visited 리스트를 maps의 크기만큼 False로 초기화 한다.

visited 리스트는 해당 위치에 방문한 여부를 확인할 수 있으며, 방문했다면 탐색을 종료하는 알고리즘을 사용했다.

 

각 지점에 대해서 탐색을 시작했으며, check 함수를 통해서 재귀형식으로 4방향 탐색을 진행했다.

dfs, bfs 알고리즘을 사용해서 실행시간을 줄여주는 것이 좋지만 maps의 길이가 최대 100으므로 

총 지도의 구역은 100*100 = 10000으로 모든 탐색을 진행하기에 크지 않은 영역이기 때문에 완전탐색 알고리즘을 구성했다.

 

check 재귀함수를 통해서 새로운 지점을 방문하고, 방문한 지역의 값을 sum_data에 더하는 형식으로 문제를 풀었다.

새로운 영역을 탐색할 때는 maps의 범위를 초과하였는지, 해당 구역이 바다인지, 방문한 곳인지 확인했다.

 

 

완전 탐색으로 문제를 해결하였지만, 더 고난이도 문제가 나올 경우 dfs나 bfs 알고리즘을 사용해야 문제를 풀 수 있을 것 같다.

내 코드는 테스트 케이스를 통과하였지만, 실행 시간에서 큰 차이를 보였다.

 

다른 문제 유형에 대비해서 dfs, bfs 알고리즘을 다시 학습 해야겠다..