[Python] 17836 공주님을 구해라! 풀이

# PROBLEM - 공주님을 구해라
# TIER - G5
# NUMBER - 17836
# DATE - 2022-08-05 16:32
# IDEA - 빡구현 문제입니다
# BFS로 그냥 가는 경우, 검 줍고 벽 부수고 가는 경우 이렇게 계산해야 할듯
import sys
import collections
import copy
input = sys.stdin.readline

N, M, T = map(int, input().split())
graph = [list(map(str, input().split())) for _ in range(N)]
normal = copy.deepcopy(graph) # 리스트는 기본적으로 얕은복사가 되서 normal = graph 이런식으로 쓰면 동기화가 되어버림;
sword = copy.deepcopy(graph) # 깊은복사로 객체화

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def bfs_normal(startX, startY): # 그냥 정석적인 BFS
    normal_queue = collections.deque([(0, 0)]) 
    while normal_queue:
        x, y = normal_queue.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0 <= nx < N and 0 <= ny < M and normal[nx][ny] == '0':
                normal_queue.append((nx, ny))
                normal[nx][ny] = int(normal[x][y]) + 1
    return int(normal[-1][-1]) # 공주 위치 return


def bfs_sword(startX, startY, isSword): # 검 줍고 재귀실행 해줌
    visited = [[False] * M for _ in range(N)]
    if not isSword: # 검 줍기까지의 과정
        sword_queue = collections.deque([(0, 0)]) # 0, 0 에서 시작
        sword[startX][startY] = 1 
        while sword_queue:
            x, y = sword_queue.popleft()
            for i in range(4):
                nx, ny = x+dx[i], y+dy[i]
                if 0 <= nx < N and 0 <= ny < M:
                    if sword[nx][ny] == '0':
                        sword_queue.append((nx, ny)) 
                        sword[nx][ny] = int(sword[x][y]) + 1
                    elif sword[nx][ny] == '2': # 검에 도착
                        sword[nx][ny] = int(sword[x][y]) + 1
                        return bfs_sword(nx, ny, True) # 검 위치를 시작점으로, 검 보유여부 True
    else: # 검 줍고난 뒤
        sword_queue = collections.deque([(startX, startY)]) # 검의 위치에서 시작
        visited[startX][startY] = True
        while sword_queue:
            x, y = sword_queue.popleft()
            for i in range(4):
                nx, ny = x+dx[i], y+dy[i]
                if 0 <= nx < N and 0 <= ny < M:
                    if not visited[nx][ny]: # 검 줍고난 뒤에는 무서울게 없음 (벽 무제한 뚫기 기능)
                        sword_queue.append((nx, ny)) # graph 원소로 진입여부를 확인하는 것이 아닌
                        sword[nx][ny] = int(sword[x][y]) + 1 # visited로 확인
                        visited[nx][ny] = True
    return int(sword[-1][-1]) # 공주 위치 return 


normal_distance = bfs_normal(0, 0) # 공주 위치 return
sword_distance = bfs_sword(0, 0, False) # 공주 위치 return


if normal_distance and sword_distance: # 검X, 검O 둘다 성공시
    answer = min(normal_distance, sword_distance-1)
elif sword_distance: # 검O 만 성공시
    answer = sword_distance-1
else: # 검X 만 성공시
    answer = normal_distance

if answer > T or (not normal_distance and not sword_distance): # 제한시간이 지났거나 둘다 실패시
    print('Fail')
else:
    print(answer)