[백준] 2412번 암벽등반 _ Python

https://www.acmicpc.net/problem/2412

 

[초기 접근 방법]

1. (0, 0)에서 조건에 만족하는 홈을 찾아 큐에 넣는다.

2. bfs를 돌려가며, 각 홈에서 조건에 만족하는 홈을 찾는다. + (x, y, dis)
    조건 설정에서 틀렸다. ( '<= 2' 가 아니라 'range(-2,3)' 탐색 )

3. dis 값이 더 작은 것으로 유지한다.

4. y좌표가 T일 때 함수를 종료한다.

 

[생각]

1. O(25억)인데 시간초과가 나지 않나..
     역시 시간초과가 났고, set()을 활용해서 dot(홈)에 접근하는 속도를 높이려 했다.

2. 이 역시도 시간초과.. dot(홈)을 전부 접근하려는 게 문제였다.
     현재 위치를 중심으로, 범위 설정을 함으로써(lower_bound) 푸는 문제였다.

3. queue의 pop 개념을 사용하려면, deque.popleft()

4. '이분탐색' 문제인 줄 알았는데, 'bfs + lower_bound' 문제였다.
     (일단 카테고리는 이분탐색으로..)

 

[기존 코드(X)]

# 풀이 시간 : 40분
# 시간복잡도 : O(n^2), bfs 시간복잡도
# 공간복잡도 : O(n)
# 참고 : -

import sys
from collections import deque
input = sys.stdin.readline

# n : 홈의 개수, T : y좌표가 T가 될 때까지
n, T = map(int, input().split())

# x, y : 홈의 좌표
dot = set()
for _ in range(n):
    x, y = map(int, input().split())
    dot.add((x, y))

q = deque()
q.append((0, 0, 0))

while len(q) > 0:
    curX, curY, curDis = q.pop() # 그 지점까지 이동한 거리

    if curY == T: # y좌표가 조건 T에 도달하면
        print(curDis) # 이동한 거리를 출력하고 exit()
        exit()

    for x, y in list(dot):
        if abs(curX-x) <= 2 and abs(curY-y) <= 2:
            q.append((x, y, curDis+1))
            dot.remove((x, y))

print(-1) # 정상에 오를 수 없는 경우

 

[개선된 코드(O)]

# 풀이 시간 : 40분 + 30분
# 시간복잡도 : O(n^2), bfs 시간복잡도
# 공간복잡도 : O(n)
# 참고 : https://lagooni.tistory.com/entry/%EB%B0%B1%EC%A4%80-%EC%95%94%EB%B2%BD-%EB%93%B1%EB%B0%98-2412%EB%B2%88-Python

import sys
from collections import deque
input = sys.stdin.readline

# n : 홈의 개수, T : y좌표가 T가 될 때까지
n, T = map(int, input().split())

# x, y : 홈의 좌표
dot = set()
for _ in range(n):
    x, y = map(int, input().split())
    dot.add((x, y))

q = deque()
q.append((0, 0, 0))

while len(q) > 0:
    curX, curY, curDis = q.popleft() # 그 지점까지 이동한 거리

    if curY == T: # y좌표가 조건 T에 도달하면
        print(curDis) # 이동한 거리를 출력하고 exit()
        exit()

    # lower_bound, 다음 홈으로 갈 수 있는 범위 내만 탐색하면 된다.
    for i in range(-2, 3):
        for j in range(-2, 3):
            nx = curX + i
            ny = curY + j

            if (nx, ny) in dot:
                q.append((nx, ny, curDis + 1))
                dot.remove((nx, ny)) # 삭제하지 않으면, 이제는 더 이상 쓸모없는 홈 좌표가 큐에 계속 맴돌게 됨

print(-1) # 정상에 오를 수 없는 경우