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

 

현 위치에서 바로 행사장까지 갈 수 있다면 happy를 출력하고,

그렇지 않으면 갈 수 있는 편의점이 있는지 찾아본다.

있다면 그 편의점에서 맥주를 충전하고 위 과정을 반복한다.

모든 편의점을 들렀는데도 행사장까지 갈 수 없다면 sad를 출력하면 된다.

 

import sys
from collections import deque
input = sys.stdin.readline

# 두 좌표 사이의 거리를 구하는 함수
def dist(ax,ay,bx,by):
    return abs(ax-bx)+abs(ay-by)

def bfs(start,fest,conv):
    queue = deque()
    # 시작점을 큐에 넣음
    queue.append((start[0],start[1]))
    # 편의점 방문체크를 위한 리스트
    visited_conv = [False]*(len(conv))
    
    while queue:
        x,y = queue.popleft()
        # 현 지점에서 행사장까지 한 번에 갈 수 있다면 happy
        if dist(x,y,fest[0],fest[1])<=1000:
            print("happy")
            return
        # 미방문이고, 바로 갈 수 있는 편의점이 있는지 체크
        # 있다면 편의점에서 다시 bfs
        for i in range(len(conv)):
            if dist(x,y,conv[i][0],conv[i][1])<=1000:
                if not visited_conv[i]:
                    queue.append((conv[i][0],conv[i][1]))
                    visited_conv[i]=True
    # 행사장에 갈 수 없다면 sad를 출력
    print("sad")
    return

t = int(input())
    
for i in range(t):
    n = int(input())
    # 편의점 n개의 x,y 좌표를 저장하기 위한 리스트
    conv = []
    start = list(map(int,input().split()))
    for i in range(n):
        conv.append(list(map(int,input().split())))
    fest = list(map(int,input().split()))

    bfs(start,fest,conv)