BFS - 맥주 마시면서 걸어가기 [ 9205번 ]

처음에는 BFS로 어떻게 생각하지... DFS로 어떻게 생각하지...했다.

요즘 머리가 잘 안돌아가는 것 같다 ㅠ.ㅠ

 

쨌든 편의점의 경우에는 순서 상관없이, 모든 편의점을 방문할 필요 없이

맥주 20개로 5M  씩 총 1000M(1KM) 를 가면서 목적지까지 가면 된다.

 

그렇기 때문에 bfs를 이용해서 편의점까지 가는데 1000M 이하면 방문하면 된다.

그리고 수시로 목적지까지 바로 갈 수 있는지 체크하면서 편의점 방문 여부를 확인하면 된다.

from collections import deque

def bfs(x, y):
    q = deque([(x, y)])
    visited = [False] * n
    while q:
        x, y = q.popleft()
        if abs(x-ex) + abs(y-ey) <= 1000:
            print("happy")
            return
        
        for i in range(n):
            if not visited[i] and abs(x-convenience[i][0]) + abs(y-convenience[i][1]) <= 1000:
                q.append((convenience[i][0], convenience[i][1]))
                visited[i] = True
                
    print("sad")
    return
    
t = int(input())
result = []
for _ in range(t):
    n = int(input())
    tmp = []
    sx, sy = map(int, input().split())
    convenience = [list(map(int, input().split())) for _ in range(n)]
    ex, ey = map(int, input().split())
    bfs(sx, sy)