[Algorithm] BFS를 알고 풀어보자

13 Nov 2021

Reading time ~1 minute

오늘의 문제

https://leetcode.com/problems/flood-fill/submissions/

Dfs vs BFS

보통 그래프 또는 트리의 탐색을 할때 흔하디 흔하게 사용되는 두가지 방법이다. BFS(너비우선탐색)으로 풀어보았는데, 문제에서 현재 조회하고 있는 셀 기준으로 상하좌우에 있는 값들만 비교해주면 된다고 생각했기 때문이다. ~~recursion이나 call stack을 사용할 필요가 없으니 dfs는 아니겠거니 생각하기도~~

BFS는 LEVEL BY LEVEL, 즉 root에서 level이 하나씩 증가할때마다 같은 level의 모든 노드를 조회 후 다음 level로 이동하는 탐색방법이다. 보통 Queue 를 사용하며, while(queue.isEmpty() === false) 큐가 채워져 있는 동안 계속해서 조회하도록 한다. 조건 또는 로직에 따라 queue 조회를 종료하는 조건문이 매우 중요하다. 특정 목적지를 찾거나 최단 경로(shortest path)를 찾는 문제에 주로 사용되는 편

PseudoCode

// 기준이 되는 디폴트 숫자 standard = image[sr][sc];

level 별로 각각 노드가 있다고 그려보고, 상하좌우로 인접하는 경우에만 queue에 넣어서 조회 및 색 교체를 해준다. 1 -> standard | ||| 1 100 ||| 1 1 1

풀이 코드

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int standard = image[sr][sc];
        
        // root and Queue initial
        Cell root = new Cell(sr, sc);
        Queue<Cell> q = new LinkedList<Cell>(); 
        q.add(root);
        
        while(!q.isEmpty()){
            for (int idx = 0 ; idx < q.size(); idx++){
                // Current Node
                Cell curr = q.poll();
                int x = curr.x;
                int y = curr.y;
                
                if (image[x][y] == standard){
                    image[x][y] = newColor;
                    
                    // Index comfirm & Queue setting
                    if (y-1 >= 0) q.add(new Cell(x, y-1));
                    if (y+1 < image[0].length) q.add(new Cell(x, y+1));
                    if (x-1 >= 0) q.add(new Cell(x-1, y));
                    if (x+1 < image.length) q.add(new Cell(x+1, y));
                }
            }
            
        }
        
        return image;
    }
}

/*
    image 배열의 셀 하나당 만들어질 인스턴스. x, y는 좌표를 의미한다.
*/
public class Cell {
    int x;
    int y;
    
    public Cell(int i, int j) {
        this.x = i;
        this.y = j;
    }
}

채점 결과

Time Limit Exceeded 보완이 필요하다….ㅠ 개선해서 다시 포스팅 작성해야겠다.