[boj] 백준 17836 공주님을 구해라! python 풀이

문제

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

 

문제 풀이

시작점과 공주 위치가 고정되어 있음.

검을 찾고 공주한테 가는 경우와 바로 공주한테 가는 경우 둘 다 bfs로 구해서 비교하면 됨. 

fail하는 경우를 잘 걸러줘야함

 

코드

import sys
input = sys.stdin.readline
import collections

'''
검을 찾고 가는 경우와 공주한테 바로 가는 경우를 비교
'''
N, M, T = map(int, input().split())
INF = 100000
def bfs(MAP, start_x, start_y, target_x, target_y, flag=0):
    move = {(-1,0), (0,1), (1,0), (0,-1)}
    visited = [[0 for _ in range(M)] for _ in range(N)]

    q = collections.deque()
    q.append((start_x,start_y,0))
    visited[start_x][start_y] = 1

    while q:
        x,y,t = q.popleft()
        if x == target_x and y == target_y:
            return t

        if t>T: break

        for tx, ty in move:
            nx = x + tx
            ny = y + ty

            if 0<=nx<N and 0<=ny<M and visited[nx][ny] == 0 and MAP[nx][ny] != ( 1 + flag):
                visited[nx][ny] = 1
                q.append((nx,ny,t+1))
    return INF

MAP = []
for i in range(N):
    MAP.append(list(map(int,input().split())))
    for j in range(len(MAP[-1])):
        if 2 == MAP[-1][j]:
            gram_x, gram_y = i, MAP[-1].index(2)

t1 = bfs(MAP, 0, 0, N-1, M-1) # 시작부터 공주까지 바로
t2 = bfs(MAP, 0, 0, gram_x, gram_y) # 시작부터 검까지 
t3 = bfs(MAP, gram_x, gram_y, N-1, M-1, 1) #검부터 공주까지
    
# print(t1, t2, t3)
MIN_TIME = min(t1, t2+t3)
if t1 == INF and t2 == INF or MIN_TIME > T: #공주한테도 못가고 검도 못찾아
    print("Fail") 
else: 
    print(MIN_TIME)