백준17836 - 공주님을 구해라! (BFS) Python

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

 

해당 문제는 좌표 (1,1)에서 좌표 (n,m)까지 이동하는 문제다. 이때 1로 이루어진 벽은 이동할 수 없다. 여기까지는 일반적인 미로찾기 문제와 비슷하나, 해당 문제에는 '검'이라는 존재가 등장하는데, 이 '검'을 획득한 경우 벽을 모두 부술 수 있다는 특징이 있다.

 

문제 풀이 방식

결국은 최단 거리를 구하는 것이 목표이므로, 내가 원하는 좌표까지의 수행 시간을 반환하는 BFS 알고리즘을 구현한 뒤 해당 로직으로 하여금 검을 획득한 뒤 목표 좌표까지의 거리와 검을 거치지 않고 목표 좌표까지의 거리를 비교하는 방식으로 답을 구했다.

이때 '검'은 벽을 무시하기 때문에, 검을 획득한 뒤 목표 좌표까지의 거리는 검까지의 거리 + 검의 좌표에서 목표 좌표까지의 택시 거리라고 볼 수 있다.

이후 두 이동 거리의 최솟값을 구한 뒤, 문제에서 주어진 t와 비교하여 답을 출력하면 된다.

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()
from collections import deque

def solution (data) :
  arr = [list(map(int, v.split())) for v in data]
  n,m,t = arr.pop(0)

  gram = None
  for i in range(n) : 
    for j in range(m) :
      if arr[i][j] == 2 : gram = [j,i]

  transitToGram = BFS(arr, gram, n, m) + (n-1-gram[1]) + (m-1-gram[0])
  routeToPrincess = BFS(arr,[m-1,n-1], n, m)
  
  result = min(transitToGram, routeToPrincess)
  print(result if t >= result else 'Fail')

def BFS(matrix, target, Y,X) :
  visited = [[0 for _ in range(X)] for _ in range(Y)]
  queue = deque()
  queue.append([0,0,1])
  tx, ty = target

  directions = [[0,1],[0,-1],[1,0],[-1,0]]
  while queue :
    x,y,dist = queue.popleft()
    if visited[y][x] : continue
    visited[y][x] = dist
    for dx,dy in directions :
      nx,ny = dx + x, dy + y
      if nx == tx and ny == ty : return dist
      if verify(X,Y,nx,ny) and not visited[ny][nx] and matrix[ny][nx] != 1 :
        queue.append([nx,ny,dist+1])
    
  return float('inf')

def verify (X,Y,x,y) :
  return 0 <= x < X and 0 <= y < Y
  
solution(input_data)