SMALL

Given a binary tree, return the sum of values of nodes with even-valued grandparent. 

(A grandparent of a node is the parent of its parent, if it exists.)

If there are no nodes with an even-valued grandparent, return 0.

 

binary tree가 주어지고, 부모의 부모 ( grand parent) (할아버지)의 value가  짝수인 node의 value합을 구해라 

만약, 부모의 부모의 값이 짝수인 노드가 없다면 0을 반환해라


dfs를 이용하여 해답을 구해보자.

dfs메서드를 호출할때, 해당 노드의 부모와 부모의 부모를 파라미터로 전달하면 특정 노드에서 해당 부모의 부모의 value를 조회할 수 있다. 

    private void dfs(TreeNode node, TreeNode parent, TreeNode grandParent) {
        
        if (grandParent != null && grandParent.val % 2 == 0) {
            rst += node.val;
        }

        if (node.left != null) {
            dfs (node.left, node, parent);
        }

        if (node.right != null) {
            dfs (node.right, node, parent);
        }
    }

 

해당 메서드를 호출하는 내역을 보자

전역 변수를 사용하여 해결하는 방법이다.

    static int rst = 0;
    public int sumEvenGrandparent(TreeNode root) {
        if (root != null) {
            dfs (root, null, null);
        }
        return rst;
    }

 

만약, 전역 변수를 사용하지 않고 메서드에서 result를 반환하고 싶은 경우에는 아래와 같이 하면 해결 가능하다.

( 위의 방법과 거의 동일하다. 메서드의 반환타입만 추가되고 해당 값을 반환해주면 된다.)

    public int sumEvenGrandparent(TreeNode root) {
        int rst = 0;
        if (root != null) {
            rst = dfs (root, null, null);
        }
        return rst;
    }
    private int dfs(TreeNode node, TreeNode parent, TreeNode grandParent) {
        
        int rst = 0;
        if (grandParent != null && grandParent.val % 2 == 0) {
            rst += node.val;
        }

        if (node.left != null) {
            rst += dfs (node.left, node, parent);
        }

        if (node.right != null) {
            rst += dfs (node.right, node, parent);
        }

        return rst;
    }    
LIST
SMALL

Flood Fill 알고리즘에 대한 정의를 찾아보면 보통 아래와 같이 나온다.

주어진 시작점으로부터 연결된 영역들을 찾는 알고리즘 
다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘

 

주변에서 해당 알고리즘을 사용하는 케이스는 보통 아래와 같다

  • 그림판 프로그램의 "채우기" 기능 - 해당 영역의 주변에 모든 셀을 같은 색으로 색칠
  • 지뢰 찾기 프로그램 - 특정 셀을 클릭 시 주변에 지뢰가 없는 모든 셀을 찾아 줌

Flood Fill 알고리즘은 보통 DFS 알고리즘을 이용하여 재귀 함수를 통해 구현하거나

BFS 알고리즘을 이용하여 Queue를 이용하여 구현한다.

 

이번에는 2차원 배열에서 DFS를 사용하여 Flood Fill 관련 알고리즘 문제를 푸는 예제를 하나 보도록 하겠다. 

 

DFS는 2차원 배열의 경우에서 인접한 배열을 ( 위 - 오른쪽 - 아래 - 왼쪽 )의 순서로 방문한다고 가정하자.

그러면 해당 내용을 간단하게 의사 코드로 표현하면 아래와 같다.

void DFS_array( int x, int y) {

	visit(x,y);
    
    if (isValid(x, y +1)) { // 위의 배열 방문 
    	DFS_array ( x, y+1);
    }
    if (isValid(x+1, y)) { // 오른쪽 배열 방문 
    	DFS_array ( x+1, y);
    }
    if (isValid(x, y -1)) { // 아래 배열 방문 
    	DFS_array ( x, y-1);
    }
    if (isValid(x-1, y)) { // 왼쪽 배열 방문 
    	DFS_array ( x-1, y);
    }
}    

출처 : https://youtu.be/By77aC9Oe3Q

 

 

 

 

이동 순서 ( 위 - 오른쪽 - 아래 - 왼쪽 ) 

 

 9번에서 4방향 모두 방문한 상태로 return 

 

 8번에서 - > 10번으로 이동하여 계속 DFS 진행 

 

 

 

 

 

 

이러한 방식으로 기본적으로 2차원 배열에서 DFS가 어떻게 동작하는지 파악하였으니 

이러한 내용을 응용하여 Flood Fill 알고리즘에 적용해 보도록 하자

 

 

 

해당 그림에서 검은색은 벽이고 하얀 부분을 방문 가능한 영역이라고 했을 때, 

최종적으로 방문 할 수 있는 영역의 개수를 구하는 문제를 푼다고 해보자 

 

 

    int floodFill(int[][] metrics) {
        int cnt = 0;
        for (int i = 0; i < metrics.length; i++) {

            for (int j = 0; j < metrics[0].length; j++) {

                if (isValid(metrics[i][j])) { // 벽이 아닌 영역인지 판단, 이미 방문했는지 판단
                    cnt++;
                    DFS_array(i, j);
                }
            }
        }

        return cnt;
    }

 

LIST
SMALL
  • BFS의 개념
  • BFS에 대한 간단한 코드 설명 
  • BFS의 장단점
  • LeetCode 예시 문제 및 참고 코드

 

BFS ( Breadth First Search )는 너비 우선 탐색이라 불리는 알고리즘이다.

해당 알고리즘은 보통 DFS ( Depth First Search)와 많이 비교 된다. 

두 알고리즘은 모두 그래프를 탐색하는데 많이 사용된다.

 

그래프 탐색이란 - 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다.

예를 들어, 특정 도시에서 다른 도시로 이동을 할 수 있는지 탐색하는 것이 될 수 있다.

 

BFS는 그래프를 탐색시, 너비를 우선 해서 탐색을 하겠다는 전략이다. 

즉, 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법을 말한다.

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.

사용하는 경우는 보통  노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 방법을 선택한다.

 

출처 : https://coding-factory.tistory.com/612

위의 설명을 코드로 나타낸 간단한 의사 코드를 보면 아래와 같을 수 있다. 

void search(Node root) {
  Queue queue = new Queue();
  root.marked = true; // (방문한 노드 체크)
  queue.enqueue(root); // 큐에 추가

  // 큐가 소진될 때까지 반복한다.
  while (!queue.isEmpty()) {
    Node r = queue.dequeue(); // 큐에서 노드 추출
    r.marked = true; // (방문한 노드 체크)
    
    // 큐에서 꺼낸 노드와 인접한 노드들을 모두 차례로 방문한다.
    foreach (Node n in r.adjacent) {
      if (n.marked == false) {
        queue.enqueue(n); // 큐에 추가
      }
    }
  }
}

BFS의 장단점은 아래와 같을 수 있다

  • 장점
    • 출발 노드로 부터 목표 노드까지의 최단 경로를 보장해 준다.
  • 단점
    • BFS에 비해 코드 구현이 까다롭다.
    • Queue에 노드를 저장하다 보니, 저장공간이 준비되어있어야 한다. 

예시 문제 

1161 - Maximum Level Sum of a Binary Tree ( 이진트리의 합이 가장 큰 레벨 )

joomn11.tistory.com/37

 

513 - Find Bottom Left Tree Value ( 트리의 가장 밑의 왼쪽 값 찾기 )

joomn11.tistory.com/39

 

429 - N-ary Tree Level Order Traversal ( N-ary 트리의 레벨 순서 순회 )

joomn11.tistory.com/38

LIST
SMALL
  • DFS의 개념
  • DFS에 대한 간단한 코드 설명
  • DFS의 장단점
  • LeetCode 예시 문제 및 예시 코드

DFS는 깊이 우선 탐색이라고 불리는 알고리즘이다.

해당 알고리즘은 보통 그래프 탐색을 하는 경우에 사용된다.

 

그래프 탐색이란 - 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다.

예를 들어, 특정 도시에서 다른 도시로 이동을 할 수 있는지 탐색하는 것이 될 수 있다.

 

그래프 탐색 방식 중의 하나로 DFS ( 깊이 우선 탐색)은 

그래프를 탐색 할때 , 깊이를 우선적으로 탐색하겠다는 전략이다. 

시작점부터 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하고 넘어가는 방법이다.

스택이나 재귀함수를 통해서 구현할 수 있는데 재귀 함수가 구현이 간편하기에 대부분 재귀 함수로 구현한다.

출처: https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

해당 설명을 코드로 표현한 간단한 의사코드를 나타내면 아래와 같을 수 있다.

void search(Node root) {
  if (root == null) return;
  
  visit(root); // 1. root 노드 방문 (방문한 노드를 표시)
  
  // 2. root 노드와 인접한 정점을 모두 방문
  for each (Node n in root.adjacent) {
    if (n.visited == false) { // 3. 방문하지 않은 정점을 찾는다.
      search(n); // 4. root 노드와 인접한 정점 정점을 시작 정점으로 DFS를 시작
    }
  }
}

 

DFS의 장단점은 아래와 같을 수 있다.

 

장점 

  • 현재 경로(branch)상의 노드들만 기억하면 되므로, 저장 공간의 수요가 비교적 적음 
  • 코드가 직관적이고 상대적으로 구현하기 간단하다

단점

  • 재귀함수를 이용하기 때문에, 함수 호출 비용이 추가적으로 들어간다
  • 재귀 깊이가 지나치게 깊어지면 stack 메모리 비용을 예측하기 어렵다
  • 최단 경로를 알 수 없다 ( 단지 해당 노드를 방문할 수 있냐 없냐 만 판단할 때 쓰기 적합하다)

예시문제

1026 Maximum Difference Between Node and Ancestor ( 조상과 노드 사이의 최대 차이값 )

joomn11.tistory.com/36

 

1448 Count Good Nodes in Binary Tree ( 이진트리의 Good 노드 갯수 )

joomn11.tistory.com/35

 

1038 Binary Search Tree to Greater Sum Tree ( BST를 GreaterSumTree로 변환 )

joomn11.tistory.com/33

 

LIST

+ Recent posts