[Brute Force] 백준 16197번 : 두 동전 - Python 파이썬

 

 

생각하기 

시간 복잡도

총 10번까지만 버튼이 눌러지는 경우(4가지)를 고려하면 되는 것이기 때문에 

4^10 = 2^20 = 1048576번 이므로 1억을 넘지 않으므로 모든 경우를 살펴보면 된다 충분하다

 

브루트 포스 문제인 것은 확실하고 방법을 생각해보자

처음 문제를 보고 DFS 문제라고 생각했다

한 쪽으로 가게 되면 10번이 넘을 때까지 가서 min_num을 업데이트 하거나 -1로 만드는 것으로 생각했다.

실제로 정직한? DFS 로 구현해 본 결과 결과값 출력까지 꽤 오랜 시간이 걸렸다.

 

BFS로 생각하면서 주변 오/아/왼/위를 한번씩 검사를 하고 거기서 min_num인지 판단하고 return 시키면 좀 더 시간을 줄일 수 있었다. 

 

 

방법1

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

board = []

coin = []

for i in range(N):
    board.append(list(input().strip()))
    for j in range(M):
        if board[i][j] == 'o':
            coin.append([i, j])


# 오 아 왼 위
row = [0, 1, 0, -1]
col = [1, 0, -1, 0]

# visited_1 = [[False]*M for _ in range(N)]
# visited_2 = [[False]*M for _ in range(N)]

min_num = int(1e9)

def check_drop(x, y):
    if x<0 or x>=M or y<0 or y>=N:
        return True

    return False

def search(move, y1, x1, y2, x2):
    global min_num

    
    if move>=10:
        return
    else:
        move = move+1
        for i in range(0, 4):

            ny1 = y1 + row[i]
            nx1 = x1 + col[i]

            ny2 = y2 + row[i]
            nx2 = x2 + col[i]

            check_drop_1 = check_drop(nx1, ny1)
            check_drop_2 = check_drop(nx2, ny2)

            if check_drop_1 ^ check_drop_2:
                min_num = min(move, min_num)
                return
            elif check_drop_2 & check_drop_2:
                continue
            else:
                if board[ny1][nx1] == '#':
                    ny1, nx1 = y1, x1
                if board[ny2][nx2] == '#':
                    ny2, nx2 = y2, x2
                search(move, ny1, nx1, ny2, nx2)

search(0, coin[0][0], coin[0][1], coin[1][0], coin[1][1])


if min_num == int(1e9):
    print(-1)
else:
    print(min_num)

 

방법2 

recursive 함수에 진입하자마자 검사를 진행하는 방법이다 

하지만 이 방법은 위의 방법보다 시간이 더 오래 걸린다.

이유는 위의 방법은 오/왼/아/위 중 한개라도 정답 조건에 걸리면 min_num값을 구하고 나머지는 뛰어 넘긴다

( 단순히 버튼을 누르는 카운트를 구하는 문제이기 때문에 4가지의 버튼중 한개라도 해당 카운트에서 min_num을 먹는다면 그만 두고 return 해도 상관이 없기는 하다! )

 

반면에

아래 제시하는 방법은 4가지 버튼중 한개가 min_num을 먹는다고 하더라도 나머지 버튼인 경우까지 다 살펴보기 때문에 시간이 더 오래 걸린다

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

board = []

coin = []

for i in range(N):
    board.append(list(input().strip()))
    for j in range(M):
        if board[i][j] == 'o':
            coin.append([i, j])

# 오 아 왼 위
row = [0, 1, 0, -1]
col = [1, 0, -1, 0]

min_num = int(1e9)

def check_boundary(x, y):
    if x<0 or x>=M or y<0 or y>=N:
        return True
    return False

def search(cnt, x1, y1, x2, y2):
    global min_num

    if cnt==11 :
        return 

    if check_boundary(x1, y1) ^ check_boundary(x2, y2):
        min_num = min(cnt, min_num)
        return

    if check_boundary(x1, y1) & check_boundary(x2, y2):
        return

    
    
    for i in range(0, 4):
        nx1 = x1 + col[i]
        ny1 = y1 + row[i]
        nx2 = x2 + col[i]
        ny2 = y2 + row[i]

        if 0<=ny1<N and 0<=nx1<M and board[ny1][nx1] == '#':
            nx1, ny1 = x1, y1

        if 0<=ny2<N and 0<=nx2<M and board[ny2][nx2] == '#':
            nx2, ny2 = x2, y2

        search(cnt + 1, nx1, ny1, nx2, ny2)




search(0, coin[0][1], coin[0][0], coin[1][1], coin[1][0])

if min_num == int(1e9):
    print(-1)
else:
    print(min_num)