기억하고싶은것들

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/

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

중복되는 값이 없는 integer 배열이 주어진다.

가능한 모든 하위 집합을 반환하라.

해답에는 중복된 하위 집합을 포함하면 안 된다.

해답은 어떠한 순서도 상관없다.

가능한 모든 하위 집합을 반환하는 문제이다. 

Backtracking을 통해서 가능한 모든 조합을 탐색하고 조건이 만족하지 않는 경우는 패스해 보도록 하자.

여기서 조건이 만족하지 않는 경우는 이미 그전에 탐색에서 하위 집합에 포함된 원소이다.

    public void backtracking(List<List<Integer>> rst, ArrayList<Integer> list, int[] nums, int idx) {

        rst.add(new ArrayList<>(list));

        for (int i = idx; i < nums.length; i++) { // startIndex를 통해 이미 추가한 원소 필터링 
            list.add(nums[i]);
            backtracking(rst, list, nums, i + 1);
            list.remove(list.size() - 1);
        }
    }

그럼 다음으로 해당 메서드를 호출해주는 코드를 살펴보도록 하자.

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

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

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

• Backtracking에 대한 정의
• DFS와 비교 

백트래킹은 '조합 알고리즘 문제'에 대해 모든 가능한 해를 나열하는 것이다.

모든 조합의 수를 살펴보는 것인데 단 조건이 만족하는 경우에만 해당된다.

즉 주어진 조합을 탐색 시 답이 될만한지 판단하고 그렇지 않으면 해당 조건은 탐색을 멈추고 가지치기를 하는 것이다.

완전 탐색에서 좀 더 효율적으로 유망성을 판단하고 가지치기를 수행한다.

완전 탐색 : 여러 개의 solution을 가진 문제에서, 모든 solution을 탐색하는 전략

DFS와 비교 

대표적인 완전 탐색 방법으로는 DFS (Depth First Search, 깊이 우선 탐색)가 있다.

DFS는 현재 지점에서 방문할 곳이 있으면 재귀 호출 또는 Stack을 이용해서 계속 이동한다. 

하지만 DFS는 모든 노드를 방문하기 때문에 굳이 목표지점이 있지 않는 경로로 빠져서 비효율적인 탐색을 수행할 수도 있다.

백트래킹은 DFS에 가지치기 (Pruning)를 통해 불 필요한 탐색을 제한하는 완전 탐색 기법이다.

가지치기를 얼마나 잘하느냐에 따라서 효율이 극대화될 수 있는 방법이다.

정리하자면, 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다.