18430번 - 무기 공학

1️⃣ 완전 탐색(DFS)

 

✏️ 풀이 과정

N, M이 5까지로 굉장히 칸 수가 적은 편이기 때문에 완전 탐색을 요구하는 것을 추측해볼 수 있습니다. 문제는 부메랑 모양을 놓은 후에 빈 칸은 어떻게 처리해야 하는지, 부메랑을 놓은 상태를 어떻게 유지할지가 굉장히 어렵게 느껴진다는 것입니다.

 

이에 대한 해결방법은 DFS에서 방문 표시를 취소함으로써 구현할 수 있는 모든 경로 탐색을 이용하되 중심을 기준으로 삼아 N*M개의 칸을 탐색하는 것입니다. 즉 각 칸을 중심으로 삼아서 가능한 4개의 부메랑 모양이 가능한지 여부를 테스트하고 가능할 경우 해당 세 칸에 방문 표시 후 중심을 다음 칸(열에서 오른쪽으로 한 칸, 끝 열일 경우 다음 행의 처음)으로 이동해서 반복하는 것입니다.

 

이렇게 하면 가능한 모든 경우의 수를 셀 수 있습니다. 합계를 파라미터로 계속 들고다니면서 더하다가 마지막 행이 끝나고 행의 인덱스가 N이 되었을 때 max값을 갱신해주면 됩니다.

 

⏱ 시간 복잡도

각 칸마다 4개의 분기가 생길 수 있기 때문에 시간 복잡도는 O(4^(N*M))이 됩니다. 지수적으로 증가해서 매우 무거운 로직이지만 N과 M이 총 5개까지만 가능하고 실제로는 방문 표시 때문에 칸마다의 분기의 평균은 2개도 되지 않을 것으로 예상됩니다. 2^25가 33554432이기 때문에 대략적으로 시간 내에 해결될 것을 추측해볼 수 있습니다.

 

💻 코드

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 = Array.from(Array(N), (_, i) => input[i + 1].split(" ").map(Number));
const visited = Array.from(Array(N), () => Array(M));
let max = -Infinity;

const dfs = (r, c, sum) => {
    if (r == N) {
        if (sum > max) {
            max = sum;
        }
        return;
    }
    if (!visited[r][c]) {
        if (r - 1 >= 0 && !visited[r - 1][c]) {
            if (c - 1 >= 0 && !visited[r][c - 1]) {
                visited[r][c] = true;
                visited[r - 1][c] = true;
                visited[r][c - 1] = true;
                if (c != M - 1) {
                    dfs(
                        r,
                        c + 1,
                        sum + 2 * map[r][c] + map[r - 1][c] + map[r][c - 1]
                    );
                } else {
                    dfs(
                        r + 1,
                        0,
                        sum + 2 * map[r][c] + map[r - 1][c] + map[r][c - 1]
                    );
                }
                visited[r][c] = false;
                visited[r - 1][c] = false;
                visited[r][c - 1] = false;
            }
            if (c + 1 < M && !visited[r][c + 1]) {
                visited[r][c] = true;
                visited[r - 1][c] = true;
                visited[r][c + 1] = true;
                if (c != M - 1) {
                    dfs(
                        r,
                        c + 1,
                        sum + 2 * map[r][c] + map[r - 1][c] + map[r][c + 1]
                    );
                } else {
                    dfs(
                        r + 1,
                        0,
                        sum + 2 * map[r][c] + map[r - 1][c] + map[r][c + 1]
                    );
                }
                visited[r][c] = false;
                visited[r - 1][c] = false;
                visited[r][c + 1] = false;
            }
        }
        if (r + 1 < N && !visited[r + 1][c]) {
            if (c - 1 >= 0 && !visited[r][c - 1]) {
                visited[r][c] = true;
                visited[r + 1][c] = true;
                visited[r][c - 1] = true;
                if (c != M - 1) {
                    dfs(
                        r,
                        c + 1,
                        sum + 2 * map[r][c] + map[r + 1][c] + map[r][c - 1]
                    );
                } else {
                    dfs(
                        r + 1,
                        0,
                        sum + 2 * map[r][c] + map[r + 1][c] + map[r][c - 1]
                    );
                }
                visited[r][c] = false;
                visited[r + 1][c] = false;
                visited[r][c - 1] = false;
            }
            if (c + 1 < M && !visited[r][c + 1]) {
                visited[r][c] = true;
                visited[r + 1][c] = true;
                visited[r][c + 1] = true;
                if (c != M - 1) {
                    dfs(
                        r,
                        c + 1,
                        sum + 2 * map[r][c] + map[r + 1][c] + map[r][c + 1]
                    );
                } else {
                    dfs(
                        r + 1,
                        0,
                        sum + 2 * map[r][c] + map[r + 1][c] + map[r][c + 1]
                    );
                }
                visited[r][c] = false;
                visited[r + 1][c] = false;
                visited[r][c + 1] = false;
            }
        }
    }

    if (c != M - 1) {
        dfs(r, c + 1, sum);
    } else {
        dfs(r + 1, 0, sum);
    }
};

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