완전탐색(Brute-Force Search / Exhaustive Search)

정의

 

브루트 포스(brute force), 키 전수조사(exhaustive key search) 또는 무차별 대입(無差別代入)은 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법이다. 흔히 암호학에서 연구되나, 다른 알고리즘 분야에서도 사용되고 있다.

수학 문제를 원시적으로 푸는 방법인 '수 대입 노가다'의 학술적 개념이다.

 

컴퓨터 공학의 알고리즘 분야 특히, 문제 풀이에 있어서는 컴퓨터 CPU의 빠른 연산속도를 이용해 가능한 모든 경우의 수 및 경로를 탐색하여 해답을 도출해내는 방법이다.

 

예시 문제) 14500 테트로 미노

 

문제 분석해 보기

 

N*M 크기의 2차원 직사각 배열이 주어진다.

 

 

아래 5가지 형태를 각각 좌우 대칭 및 회전을 하여 위 숫자 직사각 배열에 1개의 도형을 올렸을 때 차지하는 숫자의 합이 최대를 만든다.

 

즉 어떤 도형을 골라서 어떻게 회전이나 대칭을 시켜서 어디에 올려야 최대값을 받을수 있냐인데,

 

입력값의 제한을 보면 (4 ≤ N, M ≤ 500)이다.

 

즉, 직사각 배열을 전체 탐색하여 각 위치마다 연산을 수행한다. 

500*500 

 

 

각 지점마다  4번만 이동하는 깊이우선탐색을 진행하면, 아래 4개의 모양의 도형은 모든 경우의 수를 헤아려 볼 수 있다. 

 

4*4 맵에서의 dfs 시간 복잡도는 인접리스트의 경우 O(V+E) => O(4^2 + (4+2)(4-1)) 대략 16+18 = 34번 연산

넉넉 잡아 40번 연산 한다 가정할때,

 

2500*40 => 100_000  충분히 반복 가능한 연산 횟수 모든 경우의 수를 확인해도 시간에서 문제가 되지 않는다.

 

★➡⬇⬅

 

 

 

★➡➡➡

 

★⬇⬇➡

 

 

 

 

★⬇➡⬇

 

 

 

예외)  중심 블록을 기준으로 새로운 2중 반복문을 돌며 각 위치에 맞게 회전된 모든 형태를 고려한다. 

 

 

 

 

Code

import kotlin.math.max

var n = 0
var m = 0

lateinit var map: Array<IntArray>

val dy = arrayOf(0, 1, 0, -1)
val dx = arrayOf(1, 0, -1, 0)

var max = 0
val path = mutableSetOf<Pair<Int, Int>>()

/*
    [][][][]

    [][][]
        []

    [][]
    [][]

    []
    [][]
      []
  */
fun go(node: Pair<Int, Int>, cnt: Int) {

    if (cnt == 4) {
        var sum = 0
        for (point in path) {
            sum += map[point.first][point.second]
        }
        max = max(max, sum)
        return
    }

    for (i in 0 until 4) {
        val ny = node.first + dy[i]
        val nx = node.second + dx[i]

        if (ny !in 0 until n || nx !in 0 until m) continue
        if (ny to nx in path) continue
        path.add(ny to nx)
        go(ny to nx, cnt + 1)
        path.remove(ny to nx)
    }
}

/*
      []
    [][][]
 */
fun go2(node: Pair<Int, Int>) {

    var temp = mutableListOf<Pair<Int, Int>>()

    for (i in 0 until 4) {
        val ny = node.first + dy[i]
        val nx = node.second + dx[i]
        if (ny !in 0 until n || nx !in 0 until m) continue
        temp.add(ny to nx)
    }

    if (temp.size == 3) {
        var sum = map[node.first][node.second]
        for (p in temp) {
            sum += map[p.first][p.second]
        }
        max = max(max, sum)
    }

    if (temp.size == 4) {
        for (i in 0 until temp.size) {
            var sum = map[node.first][node.second]
            for (j in 0 until temp.size) {
                if (i == j) continue
                sum += map[temp[j].first][temp[j].second]
            }
            max = max(max, sum)
        }
    }
}

fun main() = with(System.`in`.bufferedReader()) {

    val info = readLine().split(" ").map { it.toInt() }
    n = info[0]
    m = info[1]

    map = Array(n) { intArrayOf() }
    for (i in 0 until n) {
        map[i] = readLine().split(" ").map { it.toInt() }.toIntArray()
    }

    for (i in 0 until n) {
        for (j in 0 until m) {
            go(i to j, 0)
        }
    }

    for (i in 0 until n) {
        for (j in 0 until m) {
            go2(i to j)
        }
    }
    println(max)
}