14391번 - 종이 조각

1️⃣ DFS

 

✏️ 풀이 과정

완전탐색을 요하는 문제입니다. 문제에서 요구하는 1 x X 형태의 분할을 만족하면서 모든 경우의 수를 고려하기 위해서 기본 틀을 DFS를 이용한 모든 경로 탐색으로 잡고 각각을 모양을 하나의 인덱스로 표현할 수 있도록 탐색 배열을 선언해서 for문을 통해 모든 경우를 고려했습니다.

 

격자의 수는 최대 16개까지이므로 모든 칸에 대해서 고려할 수 있도록 (0, 0)부터 시작해서 열 방향으로 이동, 최대 열에 도달하면 다음 행으로 이동하는 방식으로 탐색하는 방법을 사용했습니다.

 

각 칸에 대해 함수를 시작할 때 아직 방문처리되어있지 않다면 N+M-1가지의 경우의 수(가로 세로로 1 x X꼴을 만드는 경우의 수)를 for문을 통해 모두 고려하여 방문표시를 합니다. 이후 dfs를 재귀 호출하면서 다음 칸으로(다음 열 혹은 다음 행) 이동한 이후 재귀 호출이 끝나면 방문표시를 모두 제거(미리 배열에 저장해놓았다가 한꺼번에 해제합니다.)함으로써 다른 모든 경로 또한 고려하게 만듭니다.

 

주의할 부분은 각 모양을 따질 때 중간에 방문표시된 칸을 마주칠 수 있다는 점입니다. 이러한 경우와 해당 칸만큼 채우면 범위를 넘어가는 경우를 모두 continue처리하여 중복 혹은 범위 초과를 고려하지 않도록 만들어주어야 합니다. 또한 숫자는 문자열로 처리해서 오른쪽으로 계속 이어붙이고 마지막에 합계에 반영할 때만 숫자로 바꾸어주어야 합니다.

 

행이 N에 도달했을 때 max값을 업데이트해주고 모든 재귀 실행이 끝났을 때 max값을 출력해주면 문제가 해결됩니다.

 

⏱ 시간 복잡도

모든 경로를 탐색하는 경우 시간 복잡도 계산이 매우 어려우나 N이 4까지 가능하기 때문에 완전탐색을 요하는 것을 추측할 수 있습니다.

 

💻 코드

JavaScript

const input = require("fs")
    .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
    .toString()
    .trim()
    .split("\n");

const [N, M] = input[0].split(" ").map(Number);
const map = [];
for (let i = 1; i <= N; i++) {
    map[i - 1] = input[i].split("");
}

const visited = Array.from(Array(N), () => Array(M).fill(false));
const dr = [];
const dc = [];
for (let i = 0; i < M; i++) {
    dr[i] = 0;
    dc[i] = i;
}
for (let i = M; i < M + N - 1; i++) {
    dr[i] = i - M + 1;
    dc[i] = 0;
}

let max = 0;
const dfs = (r, c, sum) => {
    if (r === N) {
        if (sum > max) {
            max = sum;
        }
        return;
    }
    if (visited[r][c]) {
        if (c !== M - 1) {
            dfs(r, c + 1, sum);
        } else {
            dfs(r + 1, 0, sum);
        }
        return;
    } else {
        loop: for (let i = 0; i < N + M - 1; i++) {
            const nr = r + dr[i];
            const nc = c + dc[i];
            if (nr >= N) continue;
            if (nc >= M) continue;
            let tmp = "";
            const store = [];
            if (dr[i] === 0) {
                for (let j = c; j <= nc; j++) {
                    if (visited[nr][j]) {
                        store.forEach((item) => {
                            visited[item[0]][item[1]] = false;
                        });
                        continue loop;
                    }
                    visited[nr][j] = true;
                    tmp += map[nr][j];
                    store.push([nr, j]);
                }
            } else {
                for (let j = r; j <= nr; j++) {
                    if (visited[j][nc]) {
                        store.forEach((item) => {
                            visited[item[0]][item[1]] = false;
                        });
                        continue loop;
                    }
                    visited[j][nc] = true;
                    tmp += map[j][nc];
                    store.push([j, nc]);
                }
            }
            if (c !== M - 1) {
                dfs(r, c + 1, sum + Number(tmp));
            } else {
                dfs(r + 1, 0, sum + Number(tmp));
            }
            store.forEach((item) => {
                visited[item[0]][item[1]] = false;
            });
        }
    }
};

dfs(0, 0, 0);
console.log(max);