오늘의 문제
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
보완이 필요하다….ㅠ 개선해서 다시 포스팅 작성해야겠다.