[백준] 9205 파이썬(python) : 맥주 마시면서 걸어가기 - (★)

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

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

 

 

맥주병의 최대 수는 20개이고 50미터 걸을때마다 한병씩 마셔야 한다 했으니 노드들 사이의 거리는 1000미터를 넘길 수 없다. 그래서 각 노드의 위치와 최종목적지의 위치가 1000미터 안에 들어올때 happy를 출력할 수 있다. 시작점 또는 모든 편의점의 위치에서 1000미터 밖에 최종목적지가 있는 경우 sad를 출력해야 한다.

 

import sys
from collections import deque
t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    start_x, start_y = map(int, sys.stdin.readline().split()) #1
    graph = []
    for _ in range(n):
        x, y = map(int, sys.stdin.readline().split())
        graph.append([x, y]) #2
    end_x, end_y = map(int, sys.stdin.readline().split()) #3
    graph.append([end_x, end_y]) #4
    visit = [False]*(n+1)
    def bfs():
        q = deque()
        q.append((start_x, start_y))
        while q:
            x, y = q.popleft()
            if abs(x - end_x) + abs(y - end_y) <= 1000: #5
                print('happy')
                return
            for i in range(n):
                if not visit[i]:
                    nx, ny = graph[i] #6
                    if abs(x-nx)+abs(y-ny)<=1000: #7
                        q.append((nx, ny))
                        visit[i] = True
        print('sad') #8
        return
    bfs()

 

#1 : 시작점의 위치 입력받음

#2 : 편의점의 위치 입력받아서 리스트에 삽입

#3 : 락 페스티벌 위치 입력

#4 : 최종위치 리스트에 삽입

#5 : 만일 현재의 위치에서 페스티벌까지의 거리값이 1000이하라면 happy를 출력하고 리턴

#6 : 새로운 위치는 graph에서 꺼냄

#7 : 현재 위치와 새로운 위치가 1000이하면 q에 삽입하고 방문처리

만일 가장 가까운 편의점의 위치라도 거리가 1000보다 크다면 q에 삽입되는 원소 없이 반복문 종료

#8 : 페스티벌에 도달하지 못하면 sad출력 후 리턴