[백준_17836] 공주님을 구해라 python

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

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

# 함수들
# in_range(x, y)
def in_range(x, y):
    return 0 <= x < n and 0 <= y < m

# can_go_with_soward(x, y)
def can_go_with_soward(x, y):
    # 범위 내에 있고, 방문한 적 없으면 가능
    return in_range(x, y) and not visited[x][y]

# bfs_2()
def bfs_2():
    while q:
        x, y = q.popleft()
        dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]
        for dx, dy in zip(dxs, dys):
            nx, ny = x + dx, y + dy
            # 검 들고 갈 수 있으면
            if can_go_with_soward(nx, ny):
                # 큐에 넣어주고
                q.append((nx, ny))
                # 방문 처리 해 주고
                visited[nx][ny] = 1
                # step 배열 관리
                step[nx][ny] = step[x][y] + 1

# can_go_without_soward(x, y)
def can_go_without_soward(x, y):
    # 범위 내에 있고, 방문한 적 없으며, 벽이 아니면 가능
    return in_range(x, y) and not visited[x][y] and castle[x][y] != 1

# bfs()
def bfs():
    while q:
        x, y = q.popleft()
        dxs, dys = [-1, 1, 0, 0], [0, 0, 1, -1]
        for dx, dy in zip(dxs, dys):
            nx, ny = x + dx, y + dy
            # 검 없이도 갈 수 있다면,
            if can_go_without_soward(nx, ny):
                # 큐에 넣어주고
                q.append((nx, ny))
                # 방문 처리 해 주고
                visited[nx][ny] = 1
                # step 배열 관리
                step[nx][ny] = step[x][y] + 1

# with_soward()
def with_soward():
    
    # 전역 변수 처리
    global visited, step, castle

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

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

    # 검의 좌표 찾기
    for i in range(n):
        for j in range(m):
            if castle[i][j] == 2:
                soward_x, soward_y = i, j

    # 큐에 좌표 넣어주고
    q.append((0, 0))
    # 방문 처리 해 주고
    visited[0][0] = 1
    # bfs 돌려주기
    bfs()

    # 검까지 도달했는지 확인
    if not visited[soward_x][soward_y]:
        return False
    
    # 도달했다면, 

    # 검의 step 배열 자리를 제외한 모든 step 배열 초기화
    for i in range(n):
        for j in range(m):
            if not (i == soward_x and j == soward_y):
                step[i][j] = 0
    
    # visited도 초기화
    visited = [
        [0] * m
        for _ in range(n)
    ]

    # 검의 자리부터 bfs_2 시작 이번엔 벽도 넘어갈 수 있음
    q.append((soward_x, soward_y))
    visited[soward_x][soward_y] = 1
    bfs_2()

    # 시간 초과 아닌지 확인 후
    if step[-1][-1] > t:
        return False
    
    # 리턴
    return step[-1][-1]

# without_soward()
def without_soward():
    
    # 전역 변수 처리
    global visited, step

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

    # 큐에 좌표 넣어주고,
    q.append((0, 0))
    # 방문 처리 해 주고,
    visited[0][0] = 1
    # bfs 돌려주기
    bfs()

    # 방문 실패 확인
    if not visited[-1][-1]:
        return False
    
    # 시간 확인 후 실패 여부 한번 더 확인
    if step[-1][-1] > t:
        return False
    
    # 성공시 리턴
    return step[-1][-1]

# 설계
# 큐 사용 준비
from collections import deque
q = deque()

# ans 설정
import sys
ans = sys.maxsize

# 검을 구하지 않고 갈 수 있는지 확인 후
if without_soward():
    # ans 처리
    ans = without_soward()

# 검을 구하고 갈 수 있는지 확인 후
if with_soward():
    # ans 처리
    ans = min(ans, with_soward())

# 검을 구하든 구하지 않든 못가면
if ans == sys.maxsize:
    # 실패
    print('Fail')
# 도착했다면,
else:
    # 정답 출력
    print(ans)