[Algorithm🧬] 백준 9205 : 맥주 마시면서 걷기

문제

처음에 생각한 것..

그냥 편의점을 주어지는 순서대로 전부 간다고 생각.

-> 검색해서 찾아보니 편의점의 안갈 수고 있고, 순서를 바꿔서 갈 수도 있다..

import sys

readl = sys.stdin.readline



t = int(readl())
for _ in range(t):
    n = int(readl()) # 편의점 개수
    positions = [list(map(int, readl().split())) for _ in range(n + 2)]

    happy = 1
    beer_count = 20


    # 집
    pre_x, pre_y = 0, 0

    # 편의점
    for i in range(1, n + 2):
        x, y = positions[i]
        dist = abs(x - pre_x) + abs(y - pre_y)

        beer_count -= (dist // 50)

        if beer_count < 0:
            happy = 0
            break


        print(beer_count)

        if i < n + 1:
            beer_count = 20

        pre_x, pre_y = x, y



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

BFS 풀이

1000 보다 작다는건 위에서도 떠올렸었는데,
지도처럼 상하좌우로 갈 수 있다는 규칙이 있는게 아니라 그냥 전체 편의점으로 갈 수 있다는게... 떠올리기 어려웠다.

import sys
from collections import deque

readl = sys.stdin.readline

def BFS():
    global happy

    q = deque()

    sx, sy = positions[0]
    q.append((sx, sy))
    visited[0] = 1

    while q:
        x, y = q.popleft()

        # 마지막 장소에서 곧장 페스티벌에 갈 수 있다면 happy
        if abs(positions[n + 1][0] - x) + abs(positions[n + 1][1] - y) <= 1000:
            happy = 1
            return

        # 페스티벌에 바로 갈 수 없다면 가까운 편의점에 들름.
        for i in range(1, n+1):
            if not visited[i]:
                nx, ny = positions[i]
                dist = abs(nx - x) + abs(ny - y)
                if dist <= 1000:
                    q.append((nx, ny))
                    visited[i] = 1


t = int(readl())
for _ in range(t):
    n = int(readl()) # 편의점 개수
    positions = [list(map(int, readl().split())) for _ in range(n + 2)]

    visited = [0] * (n + 2)
    happy = 0
    BFS()

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