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

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

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

 

나도 맥주마시면서 펜타포트 페스티벌 가고 싶다 ! 

88%에서 걸린 코드 

from collections import deque

t = int(input())

# 맨하튼 거리 계산
def distance(x1, y1, x2, y2):
    return abs(x1 - x2) + abs(y1 - y2)

def route(sx, sy, ex, ey):
    queue = deque([])
    x, y = sx, sy
    queue.append((x, y, 20))
    visited_store = [False] * n
    while queue:
        now_x, now_y, beer_count = queue.popleft()
       # print(now_x, now_y)
        # 현재 위치에서 endpoint 까지 바로 갈 수 있는지 확인하기
        d1 = distance(now_x, now_y, ex, ey)
        if d1 // 50 <= beer_count:
            return True

            # 갈 수 있는 편의점 확인하기 && 방문 여부 확인하기
        for i in range(n):
            a, b = store[i]
            if distance(now_x, now_y, a, b) // 50 <= beer_count and not visited_store[i]:
                visited_store[i] = True
                queue.append((a, b, 20))

    # bfs 실행 후 도착 못한 경우
    return False



for _ in range(t):

    n = int(input())

    sx, sy = map(int, input().split()) # 상근이네 집 start
    store = []
    for i in range(n):
        x, y = map(int, input().split()) # 편의점 좌표
        store.append((x, y))
    ex, ey = map(int, input().split()) # festival

    result = route(sx, sy, ex, ey)

    if result:
        print("happy")
    else:
        print("sad")

 

 

정답 코드 

1001 / 50 = 20...1 인 셈인데, 그러면 맥주가 21캔 필요한 것으로 봐야한다 ;;

1000m 를 기준으로 거리를 비교해야 한다 

import sys
from collections import deque

input = sys.stdin.readline
# 맨하튼 거리 계산
def distance(x1, y1, x2, y2):
    return abs(x1 - x2) + abs(y1 - y2)

def route(sx, sy, ex, ey, store):
    queue = deque([])
    x, y = sx, sy
    queue.append((x, y, 20))
    visited_store = [False] * n
    while queue:
        now_x, now_y, beer_count = queue.popleft()
        # 현재 위치에서 endpoint 까지 바로 갈 수 있는지 확인하기
        d1 = distance(now_x, now_y, ex, ey)
        if d1 <= 1000:
            print("happy")
            return

            # 갈 수 있는 편의점 확인하기 && 방문 여부 확인하기
        for i in range(n):
            a, b = store[i]
            if distance(now_x, now_y, a, b) <= 1000 and not visited_store[i]:
                visited_store[i] = True
                queue.append((a, b, 20))
    # bfs 실행 후 도착 못한 경우
    print("sad")
    return

t = int(input())

for _ in range(t):
    n = int(input())
    sx, sy = map(int, input().split()) # 상근이네 집 start
    store = []
    for i in range(n):
        x, y = map(int, input().split()) # 편의점 좌표
        store.append((x, y))
    ex, ey = map(int, input().split()) # festival

    route(sx, sy, ex, ey, store)