브루트 포스 완전 탐색 문제 - 백준 1018,1436

백준에서 단계별 풀어보기 문제를 통해 코딩테스트를 쭉쭉 풀어나가고 있다.

덕분에 파이썬 실력도 함께 향상되고 컴퓨터 방식 사고도 함께 느는 느낌이다.

 

이번 단계별 풀어보기에서 '브루트 포스'(완전탐색)문제를 다 풀어보았는데

역시나 무식하게 접근하는 방식이 빨랐다...

 

문제들 중에서 내가 생각한 풀이와 달리 쉽게 나아갔던 문제들을 몇 개 가져와봤다.

 

https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

백준에서 체스판을 칠하는 문제인데

B,W가 교차로 반복되는 문제였다.

 

보드판의 크기는 랜덤으로 주어지는데 여기서 제일 적게 수정하여 보드판을 완성하는 방법을 찾으면 된다.

 

m,n = map(int,input().split())
board = [list(input()) for _ in range(m)]
gapM,gapN = m-7,n-7

result = 32

for i in range(gapM) :
    cur = ''
    cnt = 0
    for j in range(i,i+8) :
        for k in range(gapN) :
            for l in range(k,k+8) :
                if j == 0 and l == 0 :
                    cur = board[j][l]
                    continue
                if j > 0 and l == 0 :
                    continue
                if cur == board[j][l] :
                    cnt += 1
                    if cur == 'B' :
                        cur = 'W'
                    else :
                        cur = 'B'
                else :
                    cur = board[j][l]
    if cnt == 0 :
        result = 0
        break
    if cnt < result :
        result = cnt
print(result)

이건 내가 작성한 코드이다.

보드의 크기를 입력받고 체스판은 8x8로 고정되어있으므로 그 갭을 구했다.

그리고 그 갭만큼 for문을 작성하고 8x8칸으로 주어진 보드 전체를 탐색했다.

 

cur값을 기억하여 값이 같다면 보드판을 수정해주어야하므로 cnt를 증가시켰다.

다르다면 cur값에 대입하고 넘어갔다.

그리고 체스판의 맨 첫 칸과 전 줄의 마지막 칸이 색이 동일해야하므로 continue로 넘어갔다.

for문이 끝나면 cnt값을 result에 대입하고 result를 출력했다.

 

결과는 당연히 실패했다.

아마 다음 칸으로 이동하는 줄바꿈을 처리하는 과정과

체스판이 W로 시작할 수도 있고 B로 시작할 수도 있음을 해결하지 못했다.

 

그리고 다른 답안을 참고하여 내 코드를 수정했다.

m,n = map(int,input().split())
board = [list(input()) for _ in range(m)]
gapM,gapN = m-7,n-7

result = []

for i in range(gapM) :
    for k in range(gapN) :
        draw1 = 0
        draw2 = 0
        for a in range(i,i+8) :
            for b in range(k,k+8) :
                if (a + b) % 2 == 0:
                    if board[a][b] != 'B':
                        draw1 += 1
                    if board[a][b] != 'W':
                        draw2 += 1
                else:
                    if board[a][b] != 'W':
                        draw1 += 1
                    if board[a][b] != 'B':
                        draw2 += 1
        result.append(draw1)
        result.append(draw2)
print(min(result))

기존과 다른 점은 draw변수로 B로 시작하는 체스판과 W로 시작하는 체스판을 구분했다.

그리고 board를 돌면서 B로 시작하는 체스판 board1과 W로시작하는 체스판 board2가 틀릴 경우를 모두 계산해주었다.

이후 더 작은 값을 result로 출력했다..

 

코드가 훨씬 간결해지고 이에따라 가독성도 좋아졌다.

괜히 어렵게 생각했던 것 같다..그렇다고 이 풀이를 한 번에 떠올리지도 않았을테지만 말이다..

 

https://www.acmicpc.net/problem/1436

1436번: 영화감독 숌

두 번째 문제는 666을 포함하는 숫자들 중에 n번째로 작은 수를 구하는 문제였다.

입력 조건이 n은 1보다 크거나 같고 10,000보다 작은 수였으므로

나는 단순하게 for문으로 '666'앞 뒤로 1부터 100까지 붙여가면서 sort한 뒤 마무리했다.

 

result = []
for i in range(100) :
    for j in range(100) :   
        num = str(i) + '666' + str(j)
        result.append(int(num))
result.sort()
print(result[499])

이런식으로 작성했는데 자릿수에 대한 문제를 정확하게 해결하지 못했다

내가 만든 숫자들 중에 166601과 같은 숫자들을 만들어내지 못해서 틀린 것 같았다.

 

N = int(input())
first = 666
while N != 0 :
    if '666' in str(first) :
        N -= 1
        if N == 0 :
            break;
    first += 1
print(first)

이건 답안을 참조해 작성한 코드이다.

N번째 수를 input으로부터 받아온다.

666이 가장 작은 수이므로 first에 할당해준다.

first를 1씩 증가시키며 666을 포함한다면 N에서 1을 감소시키는 while문이다

N이 0이라면 break로 탈출한다.

이렇게 하면 666부터 숫자를 세므로 자연스럽게 작은 수부터 셈이 가능하고 정확하다.

 

브루트 포스를 다 풀었는데 여전히 갈 길이 멀다...

코딩테스트를 푸는 것이 그래도 재밌어서 다행이다.

코테를 완벽하게 잘 푸는 나를 위해, 백준 랭커가 되는 날을 위해 열심히 정!진!