[LeetCode] 980. Unique Paths Ⅲ

문제 출처: https://github.com/opwe37/Algorithm-Study/blob/master/LeetCode/src/980.js

GitHub - opwe37/Algorithm-Study

---

문제

m x n 크기의 정수 배열 grid가 주어집니다. grid[i][j]는 다음과 같은 의미를 갖습니다:

• 1 은 시작 사각형을 의미합니다. 정확히 한 개의 시작 지점을 갖습니다.
• 2 는 도착 사각형을 의미합니다. 정확히 한 개의 도착 지점을 갖습니다.
• 0 은 지나갈 수 있는 빈 사각형을 의미합니다.
• -1 은 지나갈 수 없는 장애물을 의미합니다.

 

네 방향(상하좌우)으로 이동하면서, 모든 빈 사각형을 정확히 한 번씩 지나는 시작 지점에서 끝 지점까지의 경로의 수를 반환하라.

예제

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2

Explanation: We have the following two paths: 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

Input: grid = [[0,1],[2,0]]
Output: 0

Explanation: There is no path that walks over every empty square exactly once.
Note that the starting and ending square can be anywhere in the grid.

---

풀이

주어지는 grid를 그래프로 보고 DFS 기법을 사용하여 문제에 접근할 수 있습니다.

 

DFS로 grid를 탐색할 때, 임의의 지점에서 도착 지점까지 탐색을 수행하는 코드는 다음과 같습니다. 일반적으로 재귀를 통해 DFS를 구현하는 방식을 그대로 사용하여 작성하였습니다. 재귀를 종료하는 시점의 코드는 틀만 잡아 놓았습니다.

function dfs(grid, visited, [curRow, curCol]) {
    if (grid[curRow][curCol] === 2) {
    	if (모든 빈 셀 방문 체크) { return 1; }
        return 0;
    }
    
    let answer = 0;
    
    const dir = [[-1, 0], [0, 1], [1, 0], [0, -1]];
    for (let i = 0; i < 4; i++) {
        const nextRow = curRow + dir[i][0];
        const nextCol = curCol + dir[i][1];
        
        if (nextRow < 0 || nextRow >= grid.length || nextCol < 0 || nextCol >= grid[0].length) {
            continue;
        }
        if (visited[nextRow][nextCol]) { continue; }
        
        vistied[nextRow][nextCol] = true;
        answer += dfs(grid, visited, [nextRow, nextCol])
        vistied[nextRow][nextCol] = false;
    }
    
    return answer;
}

코드를 차근차근 살펴보도록 하겠습니다.

 

코드 최상단의 재귀를 종료하는 코드입니다.

if (grid[curRow][curCol] === 2) {
    if (모든 빈 셀 방문 체크) { return 1; }
    return 0;
}

현재 위치가 종료 위치라면 더 이상 재귀를 수행하지 않습니다. 반환하는 값은 두 가지 케이스로 나뉩니다. 만약 도착지점까지 오는 경로에서 모든 빈 셀을 지났다면 문제에서 요구하는 경로를 하나 찾은 것이기 때문에 1을 반환합니다. 하지만, 그렇지 않은 경우에는 0을 반환합니다.

 

다음은 경로의 이동에 관한 코드입니다. 즉, 실제 재귀를 수행하는 부분입니다.

const dir = [[-1, 0], [0, 1], [1, 0], [0, -1]];
for (let i = 0; i < 4; i++) {
    const nextRow = curRow + dir[i][0];
    const nextCol = curCol + dir[i][1];

    if (nextRow < 0 || nextRow >= grid.length || nextCol < 0 || nextCol >= grid[0].length) {
        continue;
    }
    if (visited[nextRow][nextCol]) { continue; }

    vistied[nextRow][nextCol] = true;
    answer += dfs(grid, visited, [nextRow, nextCol])
    vistied[nextRow][nextCol] = false;
}

dir 은 이동할 수 있는 위치를 담은 변수입니다. 각각 상하좌우를 표현하고 있습니다. 반복문에서 dir을 돌면서 이동 가능한 모든 케이스에 대해서 재귀를 수행합니다.

 

여기서 '이동 가능'이란, grid의 범위 안이면서 이전에 방문하지 않았던 지점을 의미합니다.

 

이 부분에서 이상한 점이 한 가지 있습니다. 왜 코드에서 grid[i][j] == -1인 경우에 대한 고려가 없지? 라는 의문이 드실 수 있습니다.

 

이것에 대해서는 저는 visited 배열을 활용하여 해결하였습니다. 현재 위에서는 visited 배열을 초기화하는 부분이 빠져있지만, visited를 초기화할 때, 장애물(grid[i][j] == -1)인 지점에 대해서는 미리 방문했다고 표시해두었습니다. 이렇게 되면 DFS 수행 시에는 방문 표시된 곳은 애초에 가지 않기 때문에 DFS에서 이 부분을 신경 쓰지 않아도 됩니다.

 

자, 이제 재귀 종료 조건 생각해봅시다. 모든 빈 셀을 방문했다는 것을 어떻게 알 수 있을까요?

 

첫 번째 방법은 visited 배열을 사용하는 것입니다. visited 배열을 순회하면서 방문하지 않은 지점이 있는지 보는 것입니다. 이 방법의 문제는 도착지점에 갈 때마다 visited배열을 샅샅이 살펴봐야 한다는 점입니다.

 

두 번째 방법은 DFS의 매개변수로 현재 남은 빈 셀의 수를 입력받는 것입니다. DFS 진입 전에 빈 셀의 수를 계산해 놓고 DFS 매개변수로 전달합니다. 재귀 호출 시 매개변수로 들어온 값을 -1 하여 전달하는 것으로 남은 빈 셀의 수를 알 수 있습니다. 단점? 이라면 단점인 것은 위의 코드에 약간의 수정이 필요하는 점인데, 시간 복잡도를 증가시키는 것보다는 훨씬 좋은 방법이니 이 방법을 사용하여 코드를 완성시키도록 하겠습니다.

 

최종 완성된 DFS함수입니다.

function dfs(grid, visited, remainEmptyCell, [curRow, curCol]) {
    if (grid[curRow][curCol] === 2) {
    	// 도착 지점일 때도 -1 해서 들어오기 때문에 이를 보정하기 위한 +1
    	remainEmptyCell += 1;
    	if (remainEmptyCell === 0) { return 1; }
        return 0;
    }
    
    let answer = 0;
    
    const dir = [[-1, 0], [0, 1], [1, 0], [0, -1]];
    for (let i = 0; i < 4; i++) {
        const nextRow = curRow + dir[i][0];
        const nextCol = curCol + dir[i][1];
        
        if (nextRow < 0 || nextRow >= grid.length || nextCol < 0 || nextCol >= grid[0].length) {
            continue;
        }
        if (visited[nextRow][nextCol]) { continue; }
        
        vistied[nextRow][nextCol] = true;
        answer += dfs(grid, visited, remainEmptyCell-1, [nextRow, nextCol])
        vistied[nextRow][nextCol] = false;
    }
    
    return answer;
}

이제 위 완성된 함수를 이용하여 문제 해결을 해보겠습니다.

var uniquePathsIII = function(grid) {
    const visited = new Array(grid.length).fill(0).map(val => new Array(grid[0].length));
    
    let startPoint = [];
    let countEmptyCell = 0;
    grid.forEach((row, rIdx) = {
    	row.forEach((val, cIdx) => {
            if (val === 1) {
            	visited[rIdx][cIdx] = true;
                startPoint = [rIdx, cIdx];
            } else if (val === -1) {
            	visited[rIdx][cIdx] = true;
            } else if (val === 0) {
            	countEmptyCell += 1;
            }
        });
    });
    
    return dfs(grid, visited, countEmptyCell, startPoint);
}

 

 

Github: 980.js

GitHub - opwe37/Algorithm-Study