Unique Paths III - DFS 알고리즘

Unique Paths III - LeetCode

문제 설명

모든 칸을 한 번씩만 지나서 목적지에 도착할 수 있는 경우의 수를 구하여라.

---

문제 해결 방안

1. DFS로 목적지를 탐색한다.

1-1. 지나갈 때 자신의 위치를 마스킹한다.

1-2. 4방향 탐색이 끝나면 다시 자신의 위치를 마스킹에서 제외한다.

1-3. 목적지에 도착하면 2단계로 넘어간다.

 

2. 모든 칸이 마스킹 되어있는지 확인한다.

2-1. 모든 칸이 마스킹 되어있다면, 조건을 만족했으므로 횟수를 센다.

2-2. 1단계로 돌아간다.

---

코드

function uniquePathsIII(grid: number[][]): number {
    let maxWidth = grid[0].length;
    let maxHeight = grid.length;
    
    // get start, end position
    let start = [];
    let end = [];
    
    // init mask
    let mask = [];
    
    for (let i = 0; i < maxHeight; i++) {
        let list = [];
        
        for (let j = 0; j < maxWidth; j++) {
            // find start and end point
            list.push(grid[i][j]);
            
            if (grid[i][j] === 1) {
                start = [i, j];
            } else if (grid[i][j] === 2) {
                end = [i, j];
            }
        }
        
        mask.push(list);
    }
    
    // DFS
    // [ [y, x, isMaskDelete], ... ]
    let [sy, sx] = start;
    // put stack 4-way of start position
    let stack = [[sy + 1, sx, false], [sy - 1, sx, false], [sy, sx + 1, false], [sy, sx -1, false]];
    let count = 0;
    
    while (stack.length > 0) {
    	// y, x: position. isMaskDelete: reset mask of this position.
        let [y, x, isMaskDelete] = stack.pop();
        
        if (x < 0 || y < 0 || x >= maxWidth || y >= maxHeight) {
            continue;
        } else if (isMaskDelete) {
        	// reset mask
            mask[y][x] = 0;
            continue;
        } else if (mask[y][x] === -1 || mask[y][x] === 1 || mask[y][x] === 3) {
            continue;
        } else if (mask[y][x] === 2) {
            // check no zero
            let noZero = true;
            
            for (let i = 0; i < maxHeight; i++) {
                for (let j = 0; j < maxWidth; j++) {
                    if (mask[i][j] === 0) {
                        noZero = false;
                        break;
                    }
                }
                
                if (!noZero) {
                    break;
                }
            }
            
            if (noZero) {
                count++;
            }        
            
            continue;
        }
        
        // mask current position
        // -1: block, 0: not visited, 1: start, 2: end, 3: visited
        mask[y][x] = 3;
        
        // reset mask of this position after 4-way search.
        // DFS use stack, so put this first.
        stack.push([y, x, true]);
        
        // 4way search
        stack.push([y + 1, x, false]);
        stack.push([y - 1, x, false]);
        stack.push([y, x + 1, false]);
        stack.push([y, x - 1, false]);
    }
    
    return count;
};