[ baekjoon ] 맥주 마시면서 걸어가기 9205번 ( python )

문제

백준 9205 맥주 마시면서 걸어가기 풀이 ( 파이썬 )

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

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

 

풀이

다익스트라를 적용해서 문제를 풀었더니 됐다. q를 돌릴 때 마다 deque에서 나오는 좌표와 목적지와의 거리의 맨해튼 거리를 확인 후 안에 있다면 flag를 True로 바꿔 happy를 출력하게 한다.

from collections import deque
import sys

input = sys.stdin.readline

t = int(input())

while t:
    n = int(input())

    store = []
    visited = [False] * (n+2)
    q = deque()

    x,y = map(int,input().split())

    q.append((x,y))

    for i in range(n):
        tx,ty = map(int,input().split())
        store.append((tx,ty))
    
    ex, ey = map(int, input().split())
    flag = False
    size = len(store)
    while q:
        cx, cy = q.popleft()

        if abs(cx - ex) + abs(cy - ey) <= 1000:
            flag = True
            break
        for i in range(size):
            if not visited[i] and abs(cx - store[i][0]) + abs(cy - store[i][1]) <= 1000:
                visited[i] = True
                q.append((store[i][0], store[i][1]))
    if flag :
        print("happy")
    else:
        print("sad")
    
    t-=1