맥주 마시면서 걸어가기

from collections import deque

def bfs():
    q = deque()
    q.append([home[0], home[1]])
    while q:
        curX, curY = q.popleft()
        # 도착 체크
        if abs(curX - target[0]) + abs(curY - target[1]) <= 1000:
            print("happy")
            return
        # 편의점들 체크
        for i in range(N):
            if not visited[i]:
                curStore = store[i]
                if abs(curX - curStore[0]) + abs(curY - curStore[1]) <= 1000:
                    visited[i] = True
                    q.append(curStore)
    print("sad")


T = int(input())
for t in range(T):
    # 입력
    N = int(input())
    home = list(map(int, input().split()))
    store = [list(map(int, input().split())) for _ in range(N)]
    target = list(map(int, input().split()))

    # bfs
    visited = [False for _ in range(N + 1)]
    bfs()

G5

BFS 로 풀면 되겠다는 생각이 처음 든다.

하지만 전형적인 BFS 문제는 아니라서 어려운 문제라고 생각했다.

내가 생각하는 전형적인 BFS 문제는 dx, dy 배열로 상하좌우 이동하며 아직 방문하지 않은 장소를 탐색하는 문제였는데,

이 문제는 그런 식으로 탐색하면 65536*65536 크기의 visited 배열을 만들고 탐색해야 한다.
메모리 초과 에러가 발생할 가능성이 매우 높다.

그렇기 때문에 조금 더 크게 보는 연습이 필요하다.
편의점 자체를 visited 배열로 설정하고 그 편의점에 도착할 수 있는지의 여부를 판단해서 bfs 방식으로 푸는 문제였다.

BFS 응용으로 좋은 연습이 됐던 문제였다.

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