ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 18430번 - 무기 공학
    알고리즘/백준 2023. 7. 19. 14:14

    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);

    '알고리즘 > 백준' 카테고리의 다른 글

    2473번 - 세 용액  (0) 2023.07.20
    2206번 - 벽 부수고 이동하기  (0) 2023.07.19
    1932번 - 정수 삼각형  (0) 2023.07.18
    13023번 - ABCDE  (0) 2023.07.18
    1865번 - 웜홀  (0) 2023.07.16
Designed by Tistory.