[백준 9205] 맥주 마시면서 걸어가기 python

 

from collections import deque

def BFS(start, finish, shop):
  visited =[]
  queue = deque()
  queue.append(start)
  visited.append(start)

  while queue:
    n = queue.pop()
    if abs(n[0] - finish[0] )+ abs(n[1]-finish[1]) <= 1000 :
      print("happy");
      return
    for el in shop:
      if el in visited:
        continue
      if el not in visited and abs(el[0] - n[0]) + abs(el[1]-n[1]) <= 1000 :
        visited.append(el)
        queue.append(el)
  print("sad")
  return        

t = int(input())
for i in range(t):
  n = int(input())
  start = list(map(int,input().split(" ")))
  shop = []
  for i in range(n):
    shop.append( list(map(int,input().split(" ")) ) )
  finish = list(map(int,input().split(" ")))
  BFS(start, finish, shop)

 

처음 문제를 봤을 때는 엥 DP인가 하고 좀 고민했지만, 

아무래도 BFS 문제집에 있었으니까.. .bfs겠지 하고 풀었다. 

 

맥주 한병당 50m를 갈 수 있고 20병을 가지고 있다 해서 50m를 단위로 하여 그래프의 노드로 삼아서 탐색해야 하나 생각했었다. 

그런데 아무리 생각해도 그러기엔 시간이 안될 것 같았다. 

 

그래서 편의점을 그래프의 노드로 삼아서 편의점을 하나씩 순회한다고 생각하니 문제를 풀 수 있었다. 

 

예전에 python 문법이 너무 자유로워서 어색했는데,

1년간 자바스크립트랑 놀다 왔더니 파이썬이랑 자스랑 제법 비슷해서 은근 쓸만하다 

 

역시근본없는애들끼리 통하는듯 . .