맥주 마시면서 걸어가기

from collections import deque
import sys
input = sys.stdin.readline
LENGTH = 65536
HALF_LENGTH = 32768
INF = 1e6

def BOJ9205() :
  global convenient_and_target
  global pentaport_x, pentaport_y
  
  def bfs(curr_x, curr_y, beer) :
    queue = deque()
    visit = []
    queue.append([curr_x, curr_y, beer])
    visit.append([curr_x, curr_y, beer])
    
    while queue :
      curr_x, curr_y, curr_beer = queue.popleft()

      if curr_x == pentaport_x and curr_y == pentaport_y :
        print("happy")
        return
      for convenient_x, convenient_y in convenient_and_target :
        if [convenient_x, convenient_y, beer] not in visit :
          dist = abs(convenient_x - curr_x) + abs(convenient_y - curr_y)
          if dist <= curr_beer * 50 :
            queue.append([convenient_x, convenient_y, curr_beer])
            visit.append([convenient_x, convenient_y, curr_beer])
    print("sad")
    return

  t = int(input())
  
  for _ in range(t) :
    beer = 20
    n = int(input())
    home_x, home_y = map(int, input().split())
    
    convenient_and_target = []
    for _ in range(n) :
      convenient_and_target.append(list(map(int, input().split())))
    
    pentaport_x, pentaport_y = map(int, input().split())
    convenient_and_target.append([pentaport_x, pentaport_y])

    bfs(home_x, home_y, beer)

BOJ9205()

 

접근 방법 :

1. 탐색을 하는 방법이 특이했다. 편의점 들과 최종 거점을 전부 비교군에 넣는다.

2. 바로 거점이 나온다면 게임 끝, 아니라면 편의점 들이 다음 bfs의 탐색대상이 된다.

3. bfs의 탐색대상에 추가되는 로직은 현재 맥주 * 50이다. 이때 맥주를 -=1 을 해주지 않은 이유는 어차피 편의점에 가면 
최대의 값인 20으로 맥주를 넣어줄테니 최대범위에서만 거리의 비교를 하고 -=1 은 해주지 않았다.

 

장애물 이였던 것 :

1. 편의점들과 거점을 한 곳에 몰아넣고 순차적으로 탐색하는 개념을 떠올리기 쉽지 않았다.

 

 

 

 

 

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

9205번: 맥주 마시면서 걸어가기