[java] Flood Fill

[참고문제] :https://leetcode.com/problems/flood-fill/

Flood Fill - LeetCode

 

문제 풀이

어려운 문제는 아니며, 기초를 다지기 위해 풀어보았다.

 

생각의 흐름 - 보자마자 떠올라야 한다.

BFS혹은 DFS 문제임을 알아야 한다.

이차원 배열과 queue, 그리고 적절한 Pair와 같은 자료구조가 필요하다.

java에서는 pair와 같은게 없기 때문에, Node라는 class를 만들어 써보자.

 

생각의 흐름 - 조건을 명확히 보자

image[sr][sc] 로 인해 넘치는 부분들을 찾아나가야 한다.

채우고자 하는 값(fill)을 명확히 하고, index 들의 제한 범위를 잘 고려하자

 

생각의 흐름 - visited 체크가 필요하다.

그냥 돌려보았더니, 갔던 길을 계속 다시 가는걸 발견했다.

이런 부분을 놓치는 경우가 많으니 항상 기초부터 다지도록 하자.

public int[][] floodFill(int[][] image, int sr, int sc, int color) {
    int N = image.length;
    int M = image[0].length;
    Queue<Node> que = new LinkedList<>();
    int[][] isVisited = new int[N][M];
    int fill = image[sr][sc];
    que.add(new Node(sr,sc));
    while(!que.isEmpty()) {
        Node node = que.poll();
        if(isVisited[node.row][node.col] != -1) {
            isVisited[node.row][node.col] = -1;
            image[node.row][node.col] = color;
            if(node.row -1 >= 0 && image[node.row -1][node.col] == fill)
                que.add(new Node(node.row -1, node.col));
            if(node.row+1 <= N -1 &&  image[node.row +1][node.col] == fill)
                que.add(new Node(node.row +1, node.col));
            if(node.col -1 >= 0 && image[node.row][node.col-1] == fill)
                que.add(new Node(node.row, node.col-1));
            if(node.col+1 <= M -1 &&  image[node.row][node.col+1] == fill)
                que.add(new Node(node.row, node.col+1));
        }
    }
    return image;
}

class Node {
    int row;
    int col;
    Node(int row, int col) {
        this.row = row;
        this.col = col;
    };
}