[python] 프로그래머스 - FloodFill

FloodFill과 그래프 탐색

floodfill 같은 경우엔 주어진 시작점으로부터 연결된 영역의 크기를 구하는 문제이다. (하나의 알고리즘으로 분류되는 듯하다)

영역구하기 예시

 

프로그래머스 스터디에 참가하면서 floodfill 이라는 문제를 오래 붙잡고 있었는데, 이런 문제는 쉽게 접근하자면 모든 점마다 bfs, dfs를 수행하면서 영역 별로 "조져주는" 것이 해결책임을 알아냈다! 한 번의 탐색만으로는 수행이 불가능하다. (모든 정점을 한 번씩만 방문하는 걸로는 해결이 안된다는 의미)

처음에는 dfs 풀이만을 생각해냈는데, 한 번의 dfs만으로 풀이하려 했기에 해당 풀이도 오류가 떴다 (당시엔 몰랐음 ㅎㅎ... 컴퓨터는 죄가 없다. 코드를 짜는 나에게 있다 죄는 ^^). bfs로는 도저히 어떻게 푸는 건지 감이 안와서 정답을 확인했는데 bfs와 dfs는 어디서부터 어떻게 탐색을 하는가의 문제이지 문제를 해결하는 로직에는 다름이 없음을 깨달았다.

하나의 영역 별로만 탐색을 진행하고, 영역이 같을 때에만 스택 혹은 큐에 넣어주고, visit 표시를 해주면 된다. 다만 가까운 애들 두루두루 하나씩 차근차근 해나가느냐(bfs), 하나 잡고 끝까지 조져주느냐(dfs)의 차이이다.

---

문제 설명

- 입력: nxm의 2차원 행렬 (행렬은 k개의 영역으로 이루어져있고, 이때 영역은 상하좌우로 행렬 노드의 값이 동일한 경우를 의미함)
- 요구 사항: 주어진 행렬 내에 영역이 총 몇 개 있는가?
- 제한 사항
    1) n과 m은 1 이상 250 이하의 정수 (최대 62500개의 노드가 주어짐)
    2) 행렬의 값은 1 이상 30000 미만인 정수로만 이루어짐.

위의 그림을 예시로 들면, 영역은 [1], [2,2], [3], [3], [1] 로 총 5개의 영역으로 이루어져 있다. (같은 숫자이고 인접해야 같은 영역으로 판별)

---

로직 및 풀이

BFS

로직

1. 다차원 배열 내 모든 노드에 대해 영역 탐색. 이때, 이미 영역이 판별된 노드라면 건너뛴다.
2. 영역 판별을 시작하는 노드에 대해 방문 표시
3. 해당 노드를 원소로 하는 큐를 선언
============================== 큐가 비워질 때까지 계속
4. 큐에서 노드를 dequeue
5. dequeue한 노드의 인접 정점 (4방향)에 대해 동일 영역인지 판별
6. 동일한 노드라면 큐에 넣어주고, 영역 판별이 완료되었다(방문했다)고 표시
==============================
7. 큐가 비워졌다면, 하나의 영역에 대해 판별이 완료됨. → 정답 카운트 +1
8. 모든 영역이 다 판별이 된다면 종료.

아래는 BFS 풀이 과정을 도식화한 것이다.

floodfill solution 1

floodfill solution 2

           

코드

위의 로직을 코드로 표현하면 다음과 같다. 큐에 삽입하는 것은 각 노드의 식별자여야 한다 (그래프 몇 번 노드를 방문했는지 식별해야 하기 때문). 따라서 이미지 배열의 값이 아닌 인덱스를 넣어줘야 한다.
그래프 탐색 시 방문을 어떻게 정의할 것인지가 중요하다. 단순히 해당 노드 값에 접근했다는 사실만으로 방문이 아닐 수 있으니 이런 부분을 유의하자.

from collections import deque

def solution(n, m, image):
    # bfs 풀이 -> 큐를 인덱스에 넣어줘야겠다.
    answer = 0
    visited = [[False for _ in range(m)] for _ in range(n)]
    direction = [(0,1),(1,0),(-1,0),(0,-1)]
    
    for py in range(n):
        for px in range(m):
            if visited[py][px]:
                continue
                
            visited[py][px] = True
            Q = deque([(py,px)])
            cur_area = image[py][px]

            while Q:
                y,x = Q.popleft()
                    
                for d in direction:
                    ny = y + d[0]
                    nx = x + d[1]

                    if (0 <= ny < n and 0 <= nx < m) and not visited[ny][nx] and image[ny][nx] == cur_area:
                        visited[ny][nx] = True
                        Q.append((ny,nx))

            answer += 1

    return answer

 

 

DFS

로직

로직은 BFS 풀이와 동일하다. 다만, 어떤 순서로 노드를 탐색하느냐가 다르다. 위의 BFS 풀이에서는 FIFO이기 때문에 현재 정점과 가까운 인접 정점부터 큐에서 삭제되는 구조이다. 따라서, 현재 정점과 가까운 인접 정점부터 탐색을 하게 된다. 반대로 DFS는 Depth-First이기 때문에 현재 정점과 연결된 정점을 타고 들어가는 구조이다. 따라서 갈림길에서 하나의 길을 쭉 타고 가다가 더이상 길이 없으면 갈림길로 돌아가 다른 가지를 동일한 방식으로 탐색한다 (backtracking). 

bfs vs dfs

 

코드

재귀로 구현했다. 재귀 구현 시에 주의할 점은 종료 조건이다. 또한 python의 경우에는 재귀에 최적화된 언어가 아니기 때문에 프로그래머스 등에 제출할 시에 max recursion depth를 늘려주지 않으면 fail이 뜨니 조심하자.

def solution(n, m, image):
    answer = 0
    direction = [(1,0),(-1,0),(0,1),(0,-1)]
    visited = [[False for _ in range(m)] for _ in range(n)]

    def dfs(y, x, cur_area):

        if (y < 0 or y >= n) or (x < 0 or x >= m):
            return

        if visited[y][x]:
            return 

        if image[y][x] != cur_area:
            return
        
        visited[y][x] = True
        dfs(y-1, x, image[y][x]) # 상
        dfs(y+1, x, image[y][x]) # 하
        dfs(y, x-1, image[y][x]) # 좌
        dfs(y, x+1, image[y][x]) # 우
    
    for py in range(n):
        for px in range(m):
            if visited[py][px]:
                continue

            dfs(py, px, image[py][px])

            answer += 1


    return answer

 

---

정리

floodfill 알고리즘은 코딩테스트에서 자주 만날 수 있고, bfs와 dfs 개념을 제대로 알고 있는지 판단할 수 있는 문제 중 하나이다. 이 문제를 풀면서 bfs와 dfs의 개념을 좀 더 명확히 할 수 있었고, visited를 언제 체크해줄 건지 등의 응용이 문제 풀이에 관건이었던 것 같다. 오래 붙잡고 있었던 보람이 있었다.