맥주 마시면서 걸어가기

풀이

 BFS 그래프 탐색 문제다. 이 문제의 핵심은 visited 배열을 선정하는 것이다. 일반적으로 그래프 문제에서 visited 배열은 주로 그래프 좌표 전체다. 하지만 이 문제에서는 그래프 범위가 너무 크기 때문에 메모리 부족 혹은 시간초과 판정이 뜬다. 마침 편의점 개수도 적기 때문에 편의점의 좌표를 visited 배열에 두자. 그리고 현재 위치에서 1000m 안에 편의점 혹은 페스티벌이 있는지 검사하면 된다. 1000m 안에 편의점이 있으면 편의점 위치를 queue에 넣으면 되고 페스티벌이 있으면 happy를 출력하고 종료하면 된다.

def bfs(house_x, house_y, festival_x, festival_y):
    queue = deque([(house_x, house_y)])
    while queue:
        current_x, current_y = queue.popleft()
        if abs(festival_x-current_x) + abs(festival_y-current_y) <= 1000:
            result.append("happy")
            return
        for i in range(n):
            store_x, store_y = store_list[i][0], store_list[i][1]
            if not v_list[i]:
                if abs(store_x-current_x) + abs(store_y-current_y) <= 1000:
                    v_list[i] = True
                    queue.append((store_x, store_y))
    result.append("sad")

for _ in range(t):
    store_list = []
    n = int(input())
    house_x, house_y = map(int, input().split())
    v_list = [False] * n
    for i in range(n):
        store_x, store_y = map(int, input().split())
        store_list.append((store_x, store_y))
    festival_x, festival_y = map(int, input().split())
    bfs(house_x, house_y,festival_x, festival_y)
for i in result:
    print(i)

시간복잡도 : O(tn)