기억하고싶은것들

Let's play the minesweeper game (Wikipedia, online game)!

You are given a 2D char matrix representing the game board. 'M' represents an unrevealedmine, 'E' represents an unrevealed empty square, 'B' represents a revealed blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, digit ('1' to '8') represents how many mines are adjacent to this revealed square, and finally 'X' represents a revealed mine.

Now given the next click position (row and column indices) among all the unrevealed squares ('M' or 'E'), return the board after revealing this position according to the following rules:

1. If a mine ('M') is revealed, then the game is over - change it to 'X'.
2. If an empty square ('E') with no adjacent mines is revealed, then change it to revealed blank ('B') and all of its adjacent unrevealed squares should be revealed recursively.
3. If an empty square ('E') with at least one adjacent mine is revealed, then change it to a digit ('1' to '8') representing the number of adjacent mines.
4. Return the board when no more squares will be revealed.

지뢰 찾기 게임을 플레이하자!

2차원의 char 배열이 주어진다.

• 'M'은 플레이어가 지뢰라고 표시해 놓은 칸
• 'E'는 눌러지지 않는 칸
• 'B'는 아무것도 없는 칸
• '숫자'는 주변에 인접한 지뢰의 개수
• 'X'는 지뢰 

다음으로, 누를 지점의 값을 input으로 입력을 받는다

그 후에 2차원 char 배열의 결과를 반환하라.

1. 만약, 'M'이 눌리면 'X'로 변환하고 게임 끝
2. 만약, 주변에 지뢰가 하나도 없는 'E'가 눌리면, 'B'로 바뀌고 해당 인접한 칸의 값을 변환
3. 만약, 주변에 지뢰가 하나 이상 있는 'E'가 눌리면, 숫자로 바꾼다.
4. 더 이상 표현할 수 있는 칸이 없을 때 2차원 배열을 반환하라

지뢰 찾기는 주변에 인접한 칸들을 방문하며 문제를 풀어가는 특징이 있다.

이러한 문제는 기존에 Graph의 Level (인접한 레벨) 별로  방문하는 BFS로 해결할 수 있다.

graph에서는 자신의 child를 방문했다면, 2차원의 배열에서는 자신에 인접한 칸들을 방문하면 된다. 

int [] dx = new int[] { 0, -1, 0, 1, 1, -1, 1, -1 };
int[] dy = new int[] { 1, 0, -1, 0, 1, -1, -1, 1 };

주변에 인접한 칸들이 방문 가능한 칸인지 판별하고, 방문이 가능하다면 queue에 담아서 순차적으로 방문을 하면 된다. 

또한, 중복적으로 방문한 칸을 들리지 않기 위해서 방문한 칸들을 기록하는 2차원의 배열을 두면 무한 반복을 막을 수 있다.

    public char[][] updateBoard(char[][] board, int[] click) {

        if (board[click[0]][click[1]] == 'M') {
            board[click[0]][click[1]] = 'X';
            return board;
        }

        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[board.length][board[0].length];

        queue.offer(click);
        visited[click[0]][click[1]] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0], y = cur[1];
            int mines = getNumberOfMines(board, x, y);

            if (mines == 0) {
                board[x][y] = 'B';

                for (int i = 0; i < 8; i++) {
                    int nx = x + dx[i], ny = y + dy[i];
                    // Check adjacent cell visitable or not 
                    if (nx >= 0 && ny >= 0 && nx < board.length && ny < board[0].length && !visited[nx][ny]) {
                        queue.offer(new int[] { nx, ny });
                        visited[nx][ny] = true; // Check this cell visited 
                    }
                }
            } else {
                board[x][y] = (char) (mines + '0');
            }
        }

        return board;
    }

추가적으로, 해당 셀 주변에 지뢰가 몇 개 있는지 판별하는 메서드를 따로 두었다.

    private int getNumberOfMines(char[][] board, int x, int y) {
        int cnt = 0;
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < board.length && ny < board[0].length) {
                cnt += board[nx][ny] == 'M' ? 1 : 0;
            }
        }
        return cnt;
    }

문제 출처 :

leetcode.com/problems/minesweeper/

Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).

이진트리의 루트가 주어지고, 트리의 각 레벨의 가장 큰 값들을 담은 배열을 반환해라. ( 0부터 시작 )

해당 문제에서는 트리의 레벨 별로 특정한 값을 찾는 문제 이므로, 트리의 레벨별로 그래프를 순환하는 bfs를 사용하여 문제를 해결해 보자.

    public List<Integer> largestValues(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> rst = new ArrayList<>();
        if (root == null) { // Check Input is Null
            return rst;
        }
        
        queue.add(root); 
        while (!queue.isEmpty()) { // Check by Tree Level
            int size = queue.size();
            int max = Integer.MIN_VALUE;

            for (int i = 0; i < size; i++) { // Only Rotate Level Node 
                TreeNode temp = queue.poll();
                if (temp.val > max) {
                    max = temp.val;
                }

                if (temp.right != null) {
                    queue.add(temp.right);
                }
                if (temp.left != null) {
                    queue.add(temp.left);
                }
            }
            rst.add(max);
        }
        return rst;
    }

Given the root of a binary tree, return the leftmost value in the last row of the tree.

이진트리의 루트가 주어지고, 트리의 가장 밑에 왼쪽 값을 리턴해라.

이 문제에서는 특정한 레벨의 값을 찾는 문제이므로, 레벨별로 트리를 탐색하는 bfs 알고리즘을 사용하는 것이 좋을 것이다. 또한 가장 왼쪽의 값이라면, bfs에서 트리를 탐색할 때 방문한 노드의 왼쪽 값부터 queue에 넣는다면 방문한 레벨의 첫 번째 값이 가장 왼쪽에 존재하는 값이 될 것이다.

    public int findBottomLeftValue(TreeNode root) {

        Queue<TreeNode> queue = new LinkedList<>();

        if (root == null) {
            return 0;
        }
        queue.add(root);

        int rst = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (i == 0) {
                    rst = node.val;
                }

                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }
        return rst;
    }

문제 출처 : 

leetcode.com/problems/find-bottom-left-tree-value/

Given an n-ary tree, return the level order traversal of its nodes' values.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

n-ary 트리가 주어지고, 노드의 값을 포함한 레벨 순서의 순회 결과를 반환해라 

Nary-Tree 입력값은 레벨 순서 순회로 표시됩니다.

각 그룹의 자식들은 null값으로 구분 지어집니다.

문제의 포인트는 결과적으로 주어진 트리의 레벨 별로 배열을 만들어 해당 배열이 포함된 결과를 반환하면 된다.

즉, 레벨 별로 어떠한 노드가 존재하는지 파악하기 위해서는 bfs를 사용하는 것이 적합하다.

    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> rst = new ArrayList<>();

        if (root == null) {
            return rst;
        }

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                Node node = queue.poll();
                list.add(node.val);

                if (node.children != null) {
                    for (Node n : node.children) {
                        queue.add(n);
                    }
                }
            }
            rst.add(list);
        }
        return rst;
    }

문제 출처 :

leetcode.com/problems/n-ary-tree-level-order-traversal/