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

문제

 

 

 

박스에 20개가 들어갈 수 잇고 50미터당 한 병이기때문에 노드별 최대 간격은 1000미터이다.

 

따라서 노드간의 간격이 1000를 넘는다면 sad가 되고 전부 1000미터 이하라면 happy를 출력하면된다.

 

사용할 알고리즘은 인접한 노드부터 간격을 체크하면 되므로 BFS를 사용해주었다.

 

 

나의 풀이

from collections import deque
def bfs():
    q = deque()
    q.append((home[0],home[1]))
    while(q):
        x,y = q.popleft()
        if abs(x-dest[0]) + abs(y-dest[1]) <= 1000:
            print("happy")
            return
        for i in range(n):
            if not visited[i]:
                nx, ny = conv[i]
                if abs(x-nx) + abs(y-ny) <= 1000:
                    q.append((nx,ny))
                    visited[i] = 1
    print("sad")
    return




t = int(input())
for i in range(t):
    n =int(input())
    home = [int(x) for x in input().split()]
    conv = []
    for j in range(n):
        x,y = map(int,input().split())
        conv.append([x,y])
    dest = [int(x) for x in input().split()]
    visited = [0 for i in range(n+1)]
    bfs()

기존의 bfs에서 1000미터 이하의 간격일때만 해당 노드를 큐에 추가해주는 방식으로 구현한다고 생각하면 된다.