BOJ 2412 - 암벽 등반 (Python)

G4, BFS

풀이

1. 시간초과

• 문제에서 주어진 암벽의 위치를 graph에 넣고 for문을 통해 해당 점을 탐색 가능 한지
  안 한지를 판단해서 가능하면 탐색
• n <= 50,000 이기에 여기서 시간초과가 발생한다고 생각

from sys import stdin
from collections import deque

n, T = map(int, stdin.readline().split())
visited = []
graph = []
for _ in range(n):
    a, b = map(int, stdin.readline().split())
    graph.append([a, b])


def bfs():
    q = deque()
    q.append([0, 0, 0])
    visited.append([0, 0])

    while q:
        x, y, cnt = q.popleft()

        if y == T:
            return cnt

        for i in range(n):
            if abs(x - graph[i][0]) <= 2 and abs(y - graph[i][1]) <= 2 and [graph[i][0], graph[i][1]] not in visited:
                visited.append([graph[i][0], graph[i][1]])
                q.append([graph[i][0], graph[i][1], cnt + 1])
    return -1

print(bfs())

2. 해결

• 암벽의 위치를 통해 판단하는게 아니라 가능한 부분내에 잡을 수 있는 암벽이 있는 지 판단
• 있다면, 탐색

list 가 아닌 set()를 쓴 이유

• in을 통해 찾는 과정에서 list는 시간초과가 발생

from sys import stdin
from collections import deque

n, T = map(int, stdin.readline().split())
graph = set()
visited = set()
for _ in range(n):
    a, b = map(int, stdin.readline().split())
    graph.add((a, b))

def bfs():
    q = deque()
    q.append([0, 0, 0])
    visited.add((0,0))

    while q:
        x, y, cnt = q.popleft()

        if y == T:
            return cnt

        for i in range(-2, 3):
            for j in range(-2, 3):
                nx = x + i
                ny = y + j
                if (nx, ny) in graph and (nx, ny) not in visited:
                    q.append([nx, ny, cnt + 1])
                    visited.add((nx, ny))
    return -1

print(bfs())