[백준][플로이드 워셜] 12908. 텔레포트 3

12908. 텔레포트 3

12908번: 텔레포트 3

 

• 첫 풀이 - fail
  • 36퍼에서 틀림
    • int(1e9)하면 터짐
    • → int(1e10) or float("inf")하니까 됨

# 노드 간의 거리는 abs(y1-y2) + abs(x1-x2)

xs, ys = map(int, input().split())
xe, ye = map(int, input().split())

graph = []
graph.append((xs, ys))
distance = [[int(1e9) for _ in range(8)] for _ in range(8)]

for i in range(3):
    x1, y1, x2, y2 = map(int, input().split())
    graph.append((x1, y1))
    graph.append((x2, y2))
    idx=len(graph)
    #거리가 탤레포트보다 빠른지 확인
    distance[idx-2][idx- 1] = min(abs(x1 - x2) + abs(y1 - y2), 10)
		#반대편도 같은 값 넣어줌
    distance[idx-1][idx-2]= distance[idx-2][idx- 1]
    
graph.append((xe, ye))
# 노드 간 거리 계산
for i in range(8):
    for j in range(8):
        distance[i][j] = min(distance[i][j], abs(
            graph[i][0] - graph[j][0]) + abs(graph[i][1] - graph[j][1]))
    

# 플로이드 워셜 - 바로가느냐, 거쳐서 가느냐
for k in range(8):
    for i in range(8):
        for j in range(8):
            distance[i][j] = min(
                distance[i][j], distance[i][k] + distance[k][j])


print(distance[0][7])

 

 

• 맞는 풀이

# 노드 간의 거리는 abs(y1-y2) + abs(x1-x2)

xs, ys = map(int, input().split())
xe, ye = map(int, input().split())

graph = []
graph.append((xs, ys))
distance = [[int(1e9) for _ in range(8)] for _ in range(8)]

for i in range(3):
    x1, y1, x2, y2 = map(int, input().split())
    graph.append((x1, y1))
    graph.append((x2, y2))
    idx=len(graph)
    #거리가 탤레포트보다 빠른지 확인
    distance[idx-2][idx- 1] = min(abs(x1 - x2) + abs(y1 - y2), 10)
		#반대편도 같은 값 넣어줌
    distance[idx-1][idx-2]= distance[idx-2][idx- 1]
    
graph.append((xe, ye))
# 노드 간 거리 계산
for i in range(8):
    for j in range(8):
        distance[i][j] = min(distance[i][j], abs(
            graph[i][0] - graph[j][0]) + abs(graph[i][1] - graph[j][1]))
    

# 플로이드 워셜 - 바로가느냐, 거쳐서 가느냐
for k in range(8):
    for i in range(8):
        for j in range(8):
            distance[i][j] = min(
                distance[i][j], distance[i][k] + distance[k][j])


print(distance[0][7])