[BOJ] 9205. 맥주 마시면서 걸어가기

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

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

 

 

1. 해결방법

맥주가 20병 있다고 한다.

50미터 이동할 때마다 맥주 한병씩은 꼭 마셔야 하는데, 여기서 맥주의 개수를 카운트 하기 보다는 
맥주를 못마시게 될 경우와 맥주를 마시면서 페스티벌에 도착하는 경우만 생각하면 되기 때문에
맥주 50미터당 맥주 20병을 다 마실 수 있는 거리인 1000미터를 기준으로 해결해야 한다.

1000미터가 키 포인트 이다.

집에서 편의점까지의 거리를 구한 다음 1000미터가 이하라면 q에 삽입하는 것을 반복하고 현재 위치를 갱신해서
페스티벌에 도착하는 거리를 계산하면 된다.

 

 

2. 정답코드

import sys
from collections import deque

input = sys.stdin.readline


def bfs():
    q = deque()
    q.append((home[0], home[1]))

    while q:
        x, y = q.popleft()
        if abs(x - fest[0]) + abs(y - fest[1]) <= 1000:
            return "happy"

        for i in range(n):
            if chk[i] == False:
                if abs(x - store[i][0]) + abs(y - store[i][1]) <= 1000:
                    chk[i] = True
                    q.append((store[i][0], store[i][1]))
    return "sad"


T = int(input())

for t in range(T):
    n = int(input())
    home = list(map(int, input().split()))
    store = []
    for _ in range(n):
        store.append(list(map(int, input().split())))

    fest = list(map(int, input().split()))
    chk = [False] * n

    print(bfs())