[BOJ/python] 2412번 암벽 등반

백준 2412번 암벽 등반 파이썬

문제 출처 - https://www.acmicpc.net/problem/2412

2412번: 암벽 등반

그래프 문제 하나 가볍게 푼다고 생각했는데 예상치 못하게 시간을 많이 소비했다. 알고리즘분석 수업에서 2차원 그래프에서 가장 가까운 두 점의 거리 문제를 다루었던 기억이 났다. 비둘기 집 원리로 접근했는데 이번 문제에서도 한 점에서 최대 25개까지만 방문할 수 있다는 점을 고려해서 문제를 접근했다.

처음에는 G 배열에 모든 좌표를 넣고 좌표 하나를 한 개의 노드로 여기고 다익스트라로 풀었다. G를 정렬해서 앞뒤로 최대 25개만 탐색하면 쉽게 풀 수 있겠다고 생각했다. 하지만 착각이었다.

G 배열을 정렬할 때 x 좌표를 우선으로 정렬을 하게 되면 x 거리가 가까워도 25개의 인덱스 내에 없을 수도 있다.

예를 들어 G=[[1,2],[1,3],…[1,100],[2,3],[2,7]] 일 때, [1,2]에서 [2,3]으로 이동할 수 있지만 G에서 인덱스 차이는 100이 넘는다.

0. 코드 (오답)

# boj-2412.py
#2412번 암벽 등반
from heapq import heappop, heappush
N,T = map(int, input().split())
G=[[0,0]]
for _ in range(N):
    G.append(list(map(int,input().split())))
G.sort(key=lambda x:(x[0],x[1]))

N+=1
dist = [ float('inf') for _ in range(N) ]

heap = [[0,0]]
dist[0]=0
while heap:
    
    cost, node = heappop(heap)
    
    if G[node][1]==T:
        sol = cost
        break
    
    if dist[node] < cost:
        continue
    
    # 비둘기집, 최대 25 인덱스 이내의 암벽으로만 이동 가능
    for next in range(node-25,node+25):
        if next<0 or next>=N:
            continue

        x,y = G[node] 
        a,b = G[next]
        if abs(x-a)<=2 and abs(y-b)<=2 and dist[next]>cost+1:
            dist[next]=cost+1
            heappush(heap, [ dist[next], next ])

print(sol)

1. 풀이

• 주어지는 좌표를 딕셔너리 형태로 저장한다.
• x,y 좌표의 차이가 2이하인 좌표들 중 최단 거리 갱신이 가능하면 방문한다.
• 다익스트라 알고리즘을 수행하며 y 좌표가 T가 되면 중단하고 답을 출력한다.

2. 코드 (정답, 다익스트라)

# boj-2412.py
#2412번 암벽 등반
from collections import deque
from heapq import heappop, heappush
N,T = map(int, input().split())
G={0:{0:1}}
dist={0:{0:float('inf')}}
for _ in range(N):
    x,y = (map(int,input().split()))
    if x in G:
        G[x][y]=1
        dist[x][y]=float('inf')
    else:
        G[x]={y:1}
        dist[x]={y:float('inf')}

sol=-1
heap=[[0,0,0]]
dist[0][0]=0
while heap:
    
    cost, x,y = heappop(heap)
    
    if y==T:
        sol = cost
        break
    
    if dist[x][y] < cost:
        continue
    
    for nx in range(x-2,x+3):
        for ny in range(y-2,y+3):
            if 0<=nx<=1000000 and 0<=ny<=T :
                if nx in G :
                    if ny in G[nx]:
                        if dist[nx][ny]>cost+1 :
                            dist[nx][ny]=cost+1
                            heappush(heap, [dist[nx][ny], nx,ny])        
print(sol)