완전 탐색

브루트 포스

무작정 모든 경우를 직접 돌려가며 탐색하는 완전탐색이다.

import sys		# 백준 2309번 - 일곱 난쟁이

# 난쟁이의 키를 담고 미리 정렬 & 키 총 합 구해둔다.
a = [0]*9
sum = 0

for x in range(9):
    a[x] = int(sys.stdin.readline())

a.sort()

for x in a:
    sum += x

# 하나를 지우고, 나머지에서 하나를 반복해서 지우는 과정을 반복한다.
def remove(a, sum):
    for x in range(9):
        b = [a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8]]
        k = sum - b[x] - 100
        del b[x]
        for y in range(8):
        	# 두번 지웠을 때 조건 맞으면 return.
            if b[y] == k:
                del b[y]
                return b


answer = remove(a, sum)

for x in answer:
    print(x)

브루트 포스의 한계

import sys		# 백준 10971번 - 외판원 순회 2 (브루트 포스)
import itertools

n = int(sys.stdin.readline())
a = [list(map(int, sys.stdin.readline().split())) for bfde in range(n)]
b = [i for i in range(n)]
min_ = 0

nPr = list(itertools.permutations(b, n))

for y in range(len(nPr)):
    k = 0
    m = 0
    c = nPr[y]
    for z in range(n-1):
        if a[c[z]][c[z+1]] != 0:
            k += a[c[z]][c[z+1]]
        else: m += 1
    if a[c[n-1]][c[0]] != 0:
            k += a[c[n-1]][c[0]]
    else: m += 1
    if y == 0: min_ = k
    if m == 0:
        min_ = min(min_, k)

print(min_)

순회하는 모든 순열을 만들어 이를 확인하였다.

하지만, 이런식의 완전탐색은 복잡도면에서 매우 불리하다. (시간초과로 실패)

import sys		# 백준 10971번 - 외판원 순회 2 (재귀 활용 DFS)

n = int(sys.stdin.readline())
a = [list(map(int, sys.stdin.readline().split())) for bfde in range(n)]
b = [0]*n
min_ = sys.maxsize

def dfs(d, s, c):
    global min_
    if d == n-1 and a[s][0] != 0:
        min_ = min(min_, c+a[s][0])
        return
    for i in range(n):
        if not b[i] and a[s][i] != 0:
            b[i] = 1
            dfs(d+1, i, c+a[s][i])
            b[i] = 0
b[0] = 1
dfs(0, 0, 0)
print(min_)

시작지점부터 경유한 지점을 체크해가며 재귀를 활용한다. (유사 Nqueen)

import sys		# 백준 2468번 - 안전 영역

sys.setrecursionlimit(100000)

# 마을 한변의 길이 n
n = int(sys.stdin.readline())

# 마을 높이정보가 담긴 2차원 배열
height = [list(map(int, sys.stdin.readline().split())) for bfde in range(n)]

# 최대 안전지역
max_area = 0

# 현재 비의 양에서 안전지역 개수
now_area = 0

# 상하좌우 안전영역 확인 재귀함수
def find_area(x, y):
    global area
    
    area[x][y] = False
    
    if x-1 >= 0:
        if area[x-1][y]: find_area(x-1,y)
    if y-1 >= 0:
        if area[x][y-1]: find_area(x,y-1)
    if x+1 < n:
        if area[x+1][y]: find_area(x+1,y)
    if y+1 < n:
        if area[x][y+1]: find_area(x,y+1)

# 비의 양을 0 ~ 100 반복
for rain in range(101):
    
    # 마을 잠김정보가 담긴 2차원 배열
    area = [[True]*n for bfde in range(n)]

    # 잠김정보 담기
    for x in range(n):
        for y in range(n):
            if height[x][y] <= rain: area[x][y] = False
    
    for x in range(n):
        for y in range(n):
            if area[x][y]:
                find_area(x, y)
                now_area += 1

    if max_area < now_area: max_area = now_area
    now_area = 0

print(max_area)

탐색 과정에 안전한 장소가 있을 시, 네 방향으로 뻗어나가며 안전한 장소를 잠김처리한다.

이 과정이 끝날때 마다 안전 영역을 count 한다.