Flood Fill (DFS)

LeetCode의 Queue, Stack 튜토리얼의 마지막 섹션의 세 번째 문제인 Flood Fill이다.

Explore - LeetCode

문제는 간단하다. 2차원 배열로 주어진 이미지 픽셀 값에 대하여 특정 위치의 좌표와 새로운 값을 주면 해당 좌표부터 시작해서 동서남북 4방향으로 탐색하며 시작 좌표와 동일한 값을 가진 픽셀을 새로운 값으로 메꿔가는 것이다. Flood Fill이라는 문제 이름처럼 그림판에서 페인트 통을 사용하는 걸 생각해보면 이해하기 쉽다.

 

이는 예전에 풀었던 Number of Islands 문제와 유사하기 때문에 비슷하게 DFS 로직을 활용하여 어렵지 않게 풀 수 있다. 처음에 작성했던 코드는 다음과 같다.

import java.util.Set;
import java.util.HashSet;


class Solution {
    private Set<String> visited = new HashSet<>();
    
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int targetColor = image[sr][sc];
        
        fillImage(image, sr, sc, targetColor, newColor);
        
        return image;
    }
    
    private void fillImage(int[][] image, int sr, int sc, int targetColor, int newColor){
        String currentPosition = String.format("%d,%d", sr, sc);
        if(visited.contains(currentPosition)) return;
        else visited.add(String.format("%d,%d", sr, sc));
        
        if(image[sr][sc] != targetColor) return;
        
        image[sr][sc] = newColor;
        
        if(sr > 0){
            fillImage(image, sr-1, sc, targetColor, newColor);
        }
        if(sr < image.length - 1){
            fillImage(image, sr+1, sc, targetColor, newColor);
        }
        if(sc > 0){
            fillImage(image, sr, sc-1, targetColor, newColor);
        }
        if(sc < image[0].length - 1){
            fillImage(image, sr, sc+1, targetColor, newColor);
        }
    }
}

그런데 이 코드는 19ms의 속도와 40MB의 좋지 않은 성능을 보였다. 이에 반해 대부분의 통계에서는 0ms, 1ms의 빠른 속도를 보이고 있는데 왜 그럴까? 여기서는 이전에 방문했던 노드를 기억하기 위해 Set 자료구조를 사용했던 게 실책이었다.

 

문제에서는 노드를 탐색하면서 픽셀 값을 바꾸기 때문에 굳이 탐색한 노드를 기억할 필요가 없다. 이전에 풀던 노드 값이 변하지 않는 문제들 때문에 Set 자료구조를 강박적으로 사용했던 게 문제였다. 대신 탐색하기 전에 원래 노드가 갖고 있어야 할 픽셀 값을 기억해두고 탐색하면서 현재 노드가 원래 픽셀 값과 다른지 비교하여 다르다면 이미 색칠된 것으로 판단하고 탐색을 중단하거나 계속할 수 있다.

 

그런데 중요한 점은 현재 노드의 픽셀 값과 원래 픽셀 값이 다른지만 가지고 판단하면 안 된다는 것이다.

위의 에러에서 볼 수 있듯이 무한루프로 인해 스택오버플로우 에러가 발생하는 경우가 있었는데 이 경우의 테스트 케이스를 확인해보니 새로 색칠하는 픽셀 값과 선택된 픽셀의 픽셀 값이 동일한 경우였다. 예를 들어 1로 색칠된 픽셀부터 다시 1로 Flood Fill 한다고 할 때 주변 노드를 탐색하던 중 현재 노드 값이 1이면 이 1이 탐색에 의해 1로 색칠된 건지 원래 1이었던 건지 구분할 수 없다. 그래서 방문했던 노드를 기억하지 못하고 계속 탐색하게 되는 문제가 발생하는 것이다.

 

그래서 필요한 로직은 색칠될 값과도 동일한지 비교하는 것이다. 위의 테스트 케이스 같은 경우 1로 색칠되어 있거나(이미 색칠됨) 1이 아니라면(색칠할 노드가 아님) 함수를 종료하도록 하는 로직을 추가해서 이를 방지할 수 있을 것이다. 이런 내용을 반영하여 개선한 코드는 다음과 같다.

class Solution {
    
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int targetColor = image[sr][sc];
        
        fillImage(image, sr, sc, targetColor, newColor);
        
        return image;
    }
    
    private void fillImage(int[][] image, int sr, int sc, int targetColor, int newColor){
        if(image[sr][sc] != targetColor || image[sr][sc] == newColor) return;
        
        image[sr][sc] = newColor;
        
        if(sr > 0){
            fillImage(image, sr-1, sc, targetColor, newColor);
        }
        if(sr < image.length - 1){
            fillImage(image, sr+1, sc, targetColor, newColor);
        }
        if(sc > 0){
            fillImage(image, sr, sc-1, targetColor, newColor);
        }
        if(sc < image[0].length - 1){
            fillImage(image, sr, sc+1, targetColor, newColor);
        }
    }
}

실행 결과 다른 풀이처럼 빠른 속도가 나오는 것을 볼 수 있었다.