문제 바로가기
문제:
수빈이는 크기가 무한대인 격자판 위에 살고 있다. 격자판의 각 점은 두 정수의 쌍 (x, y)로 나타낼 수 있다. 제일 처음에 수빈이의 위치는 (xs, ys)이고, 집이 위치한 (xe, ye)로 이동하려고 한다. 수빈이는 두 가지 방법으로 이동할 수 있다. 첫 번째 방법은 점프를 하는 것이다. 예를 들어 (x, y)에 있는 경우에 (x+1, y), (x-1, y), (x, y+1), (x, y-1)로 이동할 수 있다. 점프는 1초가 걸린다. 두 번째 방법은 텔레포트를 사용하는 것이다. 텔레포트를 할 수 있는 방법은 총 세 가지가 있으며, 미리 정해져 있다. 텔레포트는 네 좌표 (x1, y1), (x2, y2)로 나타낼 수 있으며, (x1, y1)에서 (x2, y2)로 또는 (x2, y2)에서 (x1, y1)로 이동할 수 있다는 것이다. 텔레포트는 10초가 걸린다. 수빈이의 위치와 집의 위치가 주어졌을 때, 집에 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 xs와 ys가, 둘째 줄에 xe, ye가 주어진다. (0 ≤ xs, ys, xe, ye ≤ 1,000,000,000) 셋째 줄부터 세 개의 줄에는 텔레포트의 정보 x1, y1, x2, y2가 주어진다. (0 ≤ x1, y1, x2, y2 ≤ 1,000,000,000) 입력으로 주어지는 모든 좌표 8개는 서로 다르다.
출력:
수빈이가 집에 가는 가장 빠른 시간을 출력한다.
풀이 :
이 문제는 다익스트라를 사용해도 되고 , bfs를 사용해도 된다. 플로이드 워셜 알고리즘을 사용해서 풀었다.
플로이드-워셜 이란
모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 에 사용하고
시간 복잡도는 for문을 3번 사용하기 때문에 O(N^3) 이 된다.
플로이드-워셜 알고리즘에서 가장 중요한것은
for k in range(8):
for i in range(8):
for j in range(8):
graph[i][j] = min(graph[i][k] + graph[k][j], graph[i][j])
이 부분을 사실상 암기를 해주면 되는데.
i -> j 가는 경로와 i->k->j 와 비교하면된다
여기서 k는 방문해야하는 점을 의미한다.
이 알고리즘을 문제에 적용을 하면된다.
시작점과 끝점 그리고 주어지는 점들을 spots으로 만들어준다.
총 지점은 8 개이므로 8*8 각 지점마다 값을가진 그래프를 만들어주고
graph = [[1e11] * 8 for _ in range(8)]
xs,ys -> xe,ye 만 적용해준다
graph[0][7] = graph[7][0] = cal_distance(spots[0], spots[7])
for i in range(1, 4):
x1, y1, x2, y2 = map(int, input().split())
# 거리들 순서대로 받아옴
spots[i * 2 - 1] = (x1, y1)
spots[i * 2] = (x2, y2)
# 양방향 점프가능
# 점프하는거랑 두개 사이 거리랑 가까운걸로
graph[i * 2 - 1][i * 2] = graph[i * 2][i * 2 - 1] = min(cal_distance(spots[i * 2 - 1], spots[i * 2]), 10)
각 지점들을 받아와 spots를 업데이트 해주고
점프하는것과 두개 사이거리중에 작은 값으로 업데이트 해준다.
for i in range(8):
for j in range(8):
graph[i][j] = min(graph[i][j], cal_distance(spots[i], spots[j]))그리고 모든 점의 사이값들을 또 일단 만들어준다.
그 이후의 플로이드 워셜을 죽여주면된다.
for k in range(8):
for i in range(8):
for j in range(8):
graph[i][j] = min(graph[i][k] + graph[k][j], graph[i][j])
전체 코드
import sys
xs, ys = map(int, input().split(" "))
xe, ye = map(int, input().split(" "))
def cal_distance(dot1, dot2):
return abs(dot1[0] - dot2[0]) + abs(dot1[1] - dot2[1])
spots = [0] * 8
spots[0] = (xs, ys)
spots[7] = (xe, ye)
graph = [[1e9] * 8 for _ in range(8)]
graph[0][7] = graph[7][0] = cal_distance(spots[0], spots[7])
for i in range(1, 4):
x1, y1, x2, y2 = map(int, input().split())
# 거리들 순서대로 받아옴
spots[i * 2 - 1] = (x1, y1)
spots[i * 2] = (x2, y2)
# 양방향 점프가능
# 점프하는거랑 두개 사이 거리랑 가까운걸로
graph[i * 2 - 1][i * 2] = graph[i * 2][i * 2 - 1] = min(cal_distance(spots[i * 2 - 1], spots[i * 2]), 10)
for i in range(8):
for j in range(8):
graph[i][j] = min(graph[i][j], cal_distance(spots[i], spots[j]))
for k in range(8):
for i in range(8):
for j in range(8):
graph[i][j] = min(graph[i][k] + graph[k][j], graph[i][j])
print(graph[0][7])
댓글