[061] 알고리즘: 백트래킹

 

2024.08.02(금)
 
알고리즘 6일차

특강이기에
세부 내용은 노션에 기록
티스토리에는 출퇴근 복습용 코드만 기록

 

DFS는 스택이 아닌 재귀로 푸는 것에 익숙해져야함

DP를 배울 때, 재귀 개념이 필요함 !!

=> 재귀를 이용하는 방법을 고민해야함

 

---

 

백트래킹

• solution이 될 가능성이 없는 candidate는 더 이상 탐색하지 않고 candicate를 포기(backtrack)하면서 탐색

문제: Word Search

• 이건 외우자!

문제 이해 및 해결 순서

• 실제 구현 코드

class Solution {
    int[] dr = {1, -1, 0, 0};
    int[] dc = {0, 0, 1, -1};
    boolean[][] visited;

    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        visited = new boolean[m][n];

        for(int r = 0; r < m; r++){
            for(int c = 0; c < n; c++){
                if(board[r][c] == word.charAt(0)){
                    visited[r][c] = true;
                    if(backtrack(r, c, 1, board, word)) return true;
                    visited[r][c] = false;
                }
            }
        }
        return false;
    }

    boolean backtrack(int r, int c, int count, char[][] board, String word) {
        if(count >= word.length()) return true;

        for(int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if(nr >= 0 && nr < board.length && nc >= 0 && nc < board[0].length) {
            // 아래 조건이 없었다면, 이전에 visit했던 숫자도 경로로 추가될 수 있음
                if(board[nr][nc] == word.charAt(count) && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    if(backtrack(nr, nc, count + 1, board, word)) return true;
                    visited[nr][nc] = false;
                }
            }
        }
        return false;
    }
}

 

• 배우게 되 점

백트래킹으로 공부하면서 새롭게 배우게 된 점

 

트리

• 노드들이 계층적으로 연결된 비선형 자료구조
• 노드와 부모-자식 관계의 서브트리들로 구성