1주차 스터디(23.11.09) - 완전 탐색 (Brute Force)

코딩테스트 대비 스터디를 시작하면서, 첫 주차 알고리즘은 완전 탐색(Brute Force).

 

대표문제로서 선택된 것이 프로그래머스 - 카펫 (Level 2)

 

1. 카펫

 

 

해당 문제 풀이 코드는 이하와 같습니다.

#풀이 1 (Yellow 활용)
import math
def solution1(brown, yellow):
    a = brown + yellow #전체 타일 갯수 a
    for i in range (1,int(math.sqrt(a))+1): #a = i * (a//i) = i * b (i <= b)
        if a % i == 0:
            b = a // i 
            if (i - 2) * (b - 2) == yellow: #yellow = (i-2) * (b-2)
                answer = [b,i]
                return answer

#풀이 2 (전체 활용)
def solution2(brown,yellow):
    for i in range (1,int(math.sqrt(yellow))+1): #yellow = i * (yellow//i) = i * b (i <= b)
        if yellow % i == 0:
            b = yellow // i 
            if (i + 2) * (b + 2) == brown + yellow: #brown + yellow = (i+2) * (b+2)
                answer = [b+2,i+2]
                return answer
brown,yellow = map(int,input().split())
print(solution1(brown,yellow))
print(solution2(brown,yellow))

 

첫 번째는, Yellow 타일과 Brown 타일의 개수를 합친다면 전체 타일 개수가 나온다는 점을 활용하는 풀이

 

주목할 점은 Yellow 타일의 개수 = (타일의 가로길이 - 2) * (타일의 세로길이 - 2)라는 점입니다.

 

그래서, 전체 타일 갯수 a  = i * (a // i) (가로 x 세로)로 나눈 뒤, 

 

yellow = (i - 2) * (a // i - 2)가 되는지 확인하는 방법입니다.

 

두 번째는, 첫 번째의 반대 순서로 생각해내가는 방법입니다.

 

브루트포스 방법으로 한다면, 아마 다음과 같이 되지 않을까 싶습니다.

 

이후, 따로 준비한 문제 두 개는 백준 1051번 숫자 정사각형  (실버 3), 백준 2468 안전 영역 (실버 1)이다.

 

숫자 정사각형은 정직하게 풀면 쉽게 풀리고, 안전 영역은 DFS, BFS와 연관 지을 수 있기 때문에 추가적으로 학습했다.

 

2. 숫자 정사각형

 

#BOJ 1051 숫자정사각형 실버3
N,M = map(int,input().split())
A = []
for i in range (0,N):
    a = list(str(input()))
    A.append(a)
ans = []
for i in range (1,N+1):
    for x in range (0,N-i+1):
        for y in range (0,M-i+1):
            B = list(set([A[x][y],A[x][y+i-1],A[x+i-1][y],A[x+i-1][y+i-1]]))
            if len(B) == 1:
                ans.append(i*i)
            else:
                continue
print(max(ans))

 

아이디어는 n  * n 정사각형을 생각 한 뒤, 각 정사각형의 꼭짓점이 (시작점 A[i][j]을 포함하여) A[i][j+n-1],A[i+n-1][j] , A[i+n-1][j+n-1] 으로 나타내어진다는 것에 주목하면 좋다.

 

만약, 위 네점에 해당하는 값이 전부 같다면, set 함수를 사용하여 중복되는 값들을 전부 삭제할 수 있기 때문에 set( - )의 길이는 1이 되겠다.

 

하지만 한 점이라도 해당하는 값이 다르다면, set에 의해 만들어지는 튜플의 길이가 2 이상이 되기 때문에 간단하게 판단할 수 있다.

 

ex) 1,1,1,2 -> 1,2  / 2,2,2,2 -> 2 / 3,2,3,4 -> 2,3,4 .....

 

이후, 만약 set에 의해 생성되는 튜플의 길이가 1이라면 정사각형의 넓이는 n * n 으로 주어지므로 이를 ans에 추가.

(혹은 max 함수를 사용하는 것도 좋아보인다.)

 

그 뒤 ans의 최댓값을 반환하면 끝.

 

 

3. 안전 지대

 

 

from collections import deque
N = int(input())
A = []
max_height = 0
for i in range (0,N):
    a = list(map(int,input().split()))
    max_height = max(max(a),max_height)
    A.append(a)

def move(x,y,h):
    dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
    z = []
    for i in range (0,4):
        a = x + dxdy[i][0]
        b = y + dxdy[i][1]
        if 0 <= a < N and 0 <= b < N and A[a][b] > h:
            z.append([a,b])
    return z
ans = []

for height in range (0,max_height):
    cnt = 0
    visited = [[False for _ in range (0,N)] for _ in range (0,N)]
    for i in range (0,N):
        for j in range (0,N): 
            if A[i][j] > height and visited[i][j] == False:
                visited[i][j] = True
                a = deque([])
                a.appendleft([i,j])
                while a:
                    c = a.popleft()
                    visited[c[0]][c[1]] = True
                    b = move(c[0],c[1],height)
                    for area in b:
                        if visited[area[0]][area[1]] == False:
                            visited[area[0]][area[1]] = True
                            a.appendleft([area[0],area[1]])
                cnt += 1
    ans.append(cnt)      
print(max(ans))

 

 

아이디어는 다음과 같다.

 

1. 최고 높이 max_height 구하기 (for문을 통해 0~max_height까지 전부 체크하기 위함)

 

2. DFS, BFS를 통하여 연결 요소의 갯수를 구하기

(이 과정에서 높이가 1에서 구한 변수보다 높은지 판정이 필요함)

 

3. 연결요소의 갯수를 저장하는 리스트를 만든 뒤, 그 뒤 최댓값 반환

 

느낀 점

 

브루트포스 알고리즘에서 백트래킹 (끝까지 탐색을 완료하면 뒤로 돌아가는)에 관련된 문제가 많았다는 것을 알 수 있었다.

 

또한 DFS,BFS와 연계되어있는 문제가 많아 보이므로 그 부분에 대해 추가 공부를 하는 것도 좋아 보인다.