[백준/파이썬] #2412

중간에 풀다가 꼬여서 풀이를 찾아봤다. 일단 시도했던 풀이는 다음과 같다. 

def search(dot_index, depth):
    global answer

    def find_approachable_dots(dot_index):
        left, right = dot_index, N-1
        mid = (left + right) // 2
        approachable_dots = []
        while left < right:
            if abs(graph[mid][0] - graph[left][0]) <= 2 and abs(graph[mid][1] - graph[left][1]) <= 2:
                approachable_dots.append(mid)
                # 추가 구현 필요

    if graph[dot_index][1] == T:
        answer = min(answer, depth)
    dots = find_approachable_dots(dot_index)
    for dot in dots:
        search(dot, depth+1)


if __name__ == "__main__":
    N, T = map(int, input().split())
    graph = [(0, 0)]
    answer = N
    for _ in range(N):
        x, y = map(int, input().split())
        graph.append((x, y))

    graph.sort(key=lambda x: (x[1], x[0]))
    print(graph)

 

다른 풀이를 참고해보니, 이분탐색 말고도 BFS로도 풀 수 있었다. 

from collections import deque


def bfs():
    global dots
    queue = deque()
    queue.append((0, 0, 0))
    while queue:
        x, y, count = queue.popleft()
        if y == T:
            return count
        
        for i in range(-2, 3):
            for j in range(-2, 3):
                nx = x + i
                ny = y + j
                if (nx, ny) in dots:
                    queue.append((nx, ny, count+1))
                    dots.remove((nx, ny))
    return -1
    

if __name__ == "__main__":
    N, T = map(int, input().split())
    graph = [(0, 0)]
    dots = set()
    for _ in range(N):
        x, y = map(int, input().split())
        dots.add((x, y))

    print(bfs())