기억하고싶은것들

There are n rooms labeled from 0 to n - 1 and you start in the room 0.

All the rooms labeled from 1 to n are initially locked and you cannot enter a locked room without having its key.

When you visit a room, you may find a set of distinct keys in it

and you can use them to open locked rooms and enter them.

You can visit the same room any number of times and the goal is to visit all the nrooms.

Given an array rooms where rooms [i] is the set of keys that you can obtain if you visited room i,

return true if you can visit all the rooms, or falseotherwise.

0부터 n-1까지의 이름 지어진 방이 있고, 0번째 방부터 시작된다.

1부터 n까지의 모든 방은 초반에 잠겨 있고, 열쇠가 없이는 들어갈 수 없다.

특정 방에 방문했을 때, 열쇠 꾸러미를 발견할 수 있고 그 열쇠 꾸러미를 이용해 잠긴 방을 방문할 수 있다.

방문했던 방에는 몇 번이고 중복해서 방문할 수 있고, 최종 목표는 모든 방에 방문하는 것이다.

방들의 배열이 주어지고, 해당 방에는 열쇠 꾸러미 정보를 가지고 있다.

만약 주어진 정보로 모든 방들을 방문할 수 있으면 true를 반환하고 그렇지 않으면 false를 반환하라.

주어진 방들과 열쇠들의 정보는 tree 형태로 형상화할 수 있다.

주어진 트리를 방문하며, 방문한 방들의 정보를 저장하고 모든 트리의 노드를 순회했을 때 저장한 방문한 방들의 모든 정보가 주어진 방들의 길이와 같으면 모든 방을 방문한 것이다.

recursive 한 형태로 순환을 하고, Depth First Search를 이용하여 tree를 방문하여 보자.

    public boolean canVisitAllRooms(List<List<Integer>> rooms) {

        List<Integer> visited = new ArrayList<>(); // 방문한 방들의 정보를 저장

        recursiveVisit(visited, rooms, 0); // 0번 방부터 시작

        if (visited.size() == rooms.size()) { // 주어진 방의 갯수와 방문한 방의 갯수 비교 
            return true;
        }
        return false;
    }

    private void recursiveVisit(List<Integer> visited, List<List<Integer>> rooms, int i) {

        visited.add(i);
        List<Integer> list = rooms.get(i);

        for (int idx : list) {
            if (!visited.contains(idx)) { // 이미 방문한 방은 다시 방문할 필요가 없다
                recursiveVisit(visited, rooms, idx);
            }
        }
    }

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

이진트리의 루트가 주어진다. 해당 트리의 좌우가 대칭인지 확인하여라 

이 문제는 주어진 트리가 대칭인지 판단하는 문제로, 트리를 순환하며 값을 비교해야 한다.

트리를 순환하는 방법은 크게 Iterative, Recursive와 같이 두 가지 방법이 존재한다.

이 두개의 방법을 모두 사용한 예시 코드를 각각 보도록 하자.

우선 iterative 한 방법을 보자 

해당 예시에서는 Stack을 사용하였다.

    public boolean isSymmetric_iterative(TreeNode root) {

        Stack<TreeNode> tree = new Stack<>(); // right side stack
        Stack<TreeNode> mirror = new Stack<>(); // left side stack

        tree.push(root.right);
        mirror.push(root.left);

        while (tree.size() > 0 && mirror.size() > 0) {
            TreeNode treetemp = tree.pop();
            TreeNode mirrortemp = mirror.pop();

            if (treetemp == null && mirrortemp == null) {
                continue;
            }

            if (treetemp == null || mirrortemp == null) {
                return false;
            }

            if (treetemp.val != mirrortemp.val) {
                return false;
            }

            tree.push(treetemp.left);
            mirror.push(mirrortemp.right);

            tree.push(treetemp.right);
            mirror.push(mirrortemp.left);

        }

        return true;
    }

오른쪽과 왼쪽의 노드의 대칭을 비교하기 위해서 두 개의 Stack을 이용하였다.

각각의 Stack에는 서로 대칭되는 값을 넣는다

( right에 해당하는 stack에 right node를 넣는다면, left에 해당하는 stack에는 left node를 넣는다)

그럼 다음으로 Recursive한 방법으로 주어진 트리가 대칭인지 확인하는 예시 코드를 보자

    public boolean isSymmetric_recursive(TreeNode root) {

        TreeNode right = root.right;
        TreeNode left = root.left;

        return recursive(right, left);
    }

    private boolean recursive(TreeNode right, TreeNode left) {

        if (right == null && left == null) {
            return true;
        }

        if (right == null || left == null) {
            return false;
        }

        boolean valRst = right.val == left.val;
        boolean rRst = recursive(right.right, left.left);
        boolean lRst = recursive(right.left, left.right);

        return valRst && rRst && lRst;
    }

이 방법에서는 recursive 함수를 호출시, 오른쪽 왼쪽 노드의 값을 전달하여 비교하는 방식을 취한다.

그리고 결과는 각 노드의 값 비교 및 오른쪽 recursive 및 왼쪽 recursive의 조건을 and로 묶어 결과를 반환한다

( 해당 결과 모두 true 여야 대칭이 만족 )

Given an m x n grid of characters board and a string word, return true ifword exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

m x n의 알파벳이 들어 있는 바둑판과 문자열이 주어진다, 만약 주어진 문자가 해당 바둑판에서 조합이 가능하다면 true를 리턴하라

단어는 인접한 셀의 조합으로 만들어진다, 인접한 셀은 가로, 세로로 인접한 셀들을 말한다.

같은 문자의 셀은 한번밖에 사용되지 않는다. ( 셀의 중복 사용 불가 )

먼저 주어진 바둑판에서 부터 문자열의 첫 번째 단어와 맞는 위치를 찾아야 한다.

찾아진 위치에서 부터 위, 아래, 오른쪽, 왼쪽을 방문하며 주어진 문자열에 존재하는 단어인지 비교한다.

비교한 단어가 같은 경우에는 해당 단어가 위치한 좌표를 방문한 노드로 표기하고 다시 위의 행위(찾아진 위치에서 부터 위, 아래, 오른쪽, 왼쪽을 방문하며 주어진 문자열에 존재하는 단어인지 비교)를 반복하여 전체 문자열을 찾는지 확인하면 된다. 

각각의 단어를 방문하는 부분을 Backtracking을 통해서 이미 방문한 위치이거나, 비교하려는 단어가 타깃이 아닌 경우에는 다시 뒤의 노드로 돌아가면 된다. 

    private boolean bt(char[][] board, int y, int x, String word, int idx, boolean[][] visited1) {

        if (idx == word.length()) { //문자열의 모든 단어를 찾은 경우 
            return true;
        }

        int i = board.length;
        int j = board[0].length;
        if (x < 0 || x >= j) { // 조건이 맞지 않는 경우
            return false;
        }
        if (y < 0 || y >= i) { // 조건이 맞지 않는 경우
            return false;
        }
        if (visited1[y][x]) { // 조건이 맞지 않는 경우
            return false;
        }

        if (word.charAt(idx) == board[y][x]) {
            visited1[y][x] = true;
            // 다음 노드들이 조건 맞는지 확인
            boolean rst = bt(board, y - 1, x, word, idx + 1, visited1) || 
                    bt(board, y + 1, x, word, idx + 1, visited1)|| 
                    bt(board, y, x - 1, word, idx + 1, visited1) || 
                    bt(board, y, x + 1, word, idx + 1, visited1);

            if (!rst) { 
                visited1[y][x] = false;
            } else {
                return true;
            }
        }

        return false;
    }

    public boolean exist(char[][] board, String word) {

        char start = word.charAt(0);
        boolean[][] visited1 = new boolean[board.length][board[0].length];

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

                if (board[i][j] == start) {
                    if (bt(board, i, j, word, 0, visited1)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

출처 : https://leetcode.com/problems/word-search/

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

각각 다른 숫자가 포함된 배열이 주어진다.

가능한 모든 순열을 반환하라.

어떠한 순서로든 가능하다.

가능한 모든 순열을 반환하는 문제이다.

Backtracking을 통해서 가능한 모든 조합을 탐색해 보도록 하자.

조건이 만족해서, 결과 list에 추가되는 부분

더 탐색할 하위 노드가 남아 하위 노드로 이동하는 부분으로 코드를 구분할 수 있다.

    public void backtracking(List<List<Integer>> rst, int[] nums, List<Integer> list) {
        if (list.size() == nums.length) { // 조건이 만족 하는지 확인
            rst.add(new ArrayList<>(list));
            return;
        }

        for (int i : nums) { // 더 탐색할 하위 노드 탐색
            if (!list.contains(i)) {
                list.add(i);
                backtracking(rst, nums, list);
                list.remove(list.size() - 1);
            }
        }
    }

그럼 다음으로 해당 코드를 호출해주는 부분을 살펴 보자.

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> rst = new ArrayList<>();

        backtracking(rst, nums, new ArrayList<Integer>());
        return rst;
    }

출처 : https://leetcode.com/problems/permutations/