[코드트리] k개의 벽 없애기 Python

from collections import deque
import sys

# n, k 입력
n, k = map(int, input().split())

# grid
grid = [
    list(map(int, input().split()))
    for _ in range(n)
]

# 출발 점 입력
sx, sy = map(int, input().split())
sx -= 1
sy -= 1

# 도착 점 입력
ex, ey = map(int, input().split())
ex -= 1
ey -= 1

# visited
visited = [
    [0] * n
    for _ in range(n)
]

# step 
step = [
    [0] * n
    for _ in range(n)
]

# Queue
q = deque()

# in_range(x, y)
def in_range(x, y):
    return 0 <= x and x < n and 0 <= y and y < n

# check(x, y)
def check(x, y):
    # 범위 내에 있어야하고, 방문한 적 없어야 하고, 벽이면 안됨
    return in_range(x, y) and not visited[x][y] and not grid[x][y]

# bfs()
def bfs():
    while q:
        # 언팩킹
        x, y = q.popleft()

        # dxs, dys -> 상 하 좌 우 순서 상관 x
        dxs, dys = [-1, 1, 0, 0], [0, 0, 1, -1]
        for dx, dy in zip(dxs, dys):
            # 다음 조사 위치
            nx, ny = x + dx, y + dy
            # 이동할 수 있으면
            if check(nx, ny):
                # 방문 흔적 남기고
                visited[nx][ny] = 1
                # 큐에 넣어주고
                q.append((nx, ny))
                # step에 시간 적어줌
                step[nx][ny] = step[x][y] + 1

# ans
ans = sys.maxsize

# calc()
def calc():

    global visited, step, ans

    # visited 초기화
    visited = [
        [0] * n
        for _ in range(n)
    ]

    # step 초기화
    step = [
        [0] * n
        for _ in range(n)
    ]

    # 1. 벽 치우기
    # 선택된 벽들의 좌표를 받아
    for wall in picked_walls:
        
        # 언팩킹
        x, y = wall

        # 벽 치우기 (나중에 다시 세워놔야 함)
        grid[x][y] = 0

    # 2. bfs 돌리기
    # 방문 흔적 남겨주고
    visited[sx][sy] = 1
    # 큐에 넣어주고
    q.append((sx, sy))
    # bfs 호출
    bfs()

    # 3. 최솟 값 갱신
    # 최종 위치에 찍힌 step배열의 값이 존재하고 현재 최솟값보다 작다면
    if step[ex][ey] and step[ex][ey] < ans:
        # 최솟값 갱신
        ans = step[ex][ey]

    # 4. 벽 되돌려놓기
    # 선택된 벽들의 좌표 다시 꺼내
    for wall in picked_walls:

        # 언팩킹
        x, y = wall

        # 벽 세우기
        grid[x][y] = 1
    
# 설계

# wall_list
wall_list = []

# grid 돌면서
for i in range(n):
    for j in range(n):
        # 벽을 발견하면
        if grid[i][j]:
            # 투플 형태로 wal_list에 담아 줌
            wall_list.append((i, j))

# picked_walls
picked_walls = []

# make_comb(curr_idx, cnt)
def make_comb(curr_idx, cnt):

    # 종료 조건
    if cnt == k:
        calc()
        return
    if curr_idx == len(wall_list):
        return
    
    # 넣어주고
    picked_walls.append(wall_list[curr_idx])
    # 다음 자리 호출
    make_comb(curr_idx + 1, cnt + 1)
    # 빼주고
    picked_walls.pop()

    # 무시하는 경우
    make_comb(curr_idx + 1, cnt)

# 함수 호출
make_comb(0,0)

# 출력
# 도착 못했다면
if ans == sys.maxsize:
    print(-1)
else:
    print(ans)