[백준] 16197번: 두 동전 python (백트래킹/dfs)

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

16197번: 두 동전

느리긴하지만 통과했다 ㅎㅎ.. 

문제를 처음에 제대로 안읽어서 두가지 원인으로 삽질을 했다. 

1. 동전 1개만!!!!!!! 떨어뜨려야 한다 2개 떨어뜨리는건 안되고 꼭 1개만이다 .... 

2. 벽을 만났을 때 ('#') 이동하지 않는다. 주의할 점은 벽을 만나서 이동하지 않다가 그다음 버튼누를때 다른 방향으로 이동을 시도하는 것이 가능하다는 것이다. 따라서 벽을 만났다고 해서 그 동전을 떨어뜨린 처리를 하면 안된다. 

import sys 
input = sys.stdin.readline

n, m = map(int, input().split())
board = []
coin_list = []
answer = 11
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for i in range(n):
    data = input()
    temp = []
    for j in range(m):
        if data[j] == 'o':
            coin_list.append([i, j])
        temp.append(data[j])
    board.append(temp)

# 동전의 범위 확인 
def check_range(x, y):
    if 0 <= x < n and 0 <= y < m:
        return True 
    else:
        return False 
removed = [0, 0]
def dfs(step, coins):
    global answer 
    if step > 10:
        return  
    if sum(removed) == 2:
        return  
    if sum(removed) == 1:
        answer = min(step, answer)
        return 

    for i in range(4): # 네 방향 확인 
        removed_idx = []
        new_coin = []
        for j in range(2):
            nx = coins[j][0] + dx[i]
            ny = coins[j][1] + dy[i]
            
            new_coin.append([nx, ny])
            
        for k in range(2):
            x = new_coin[k][0]
            y = new_coin[k][1]
            if not check_range(x, y):
                removed_idx.append(k)
                removed[k] = 1 
            else:
                if board[x][y] == '#': # 벽을 만나면 이동하지 않아야 하므로 이전 위치로 되돌린다 
                    new_coin[k][0] -= dx[i]
                    new_coin[k][1] -= dy[i] 
            

        dfs(step+1, new_coin)
        for j in removed_idx:
            removed[j] = 0 # 다시 동전을 살림 
        

dfs(0, coin_list)

if answer > 10:
    print(-1)
else:
    print(answer)