16958
-
백준 (BOJ) 16958번 텔레포트알고리즘 풀이/백준(Boj) 2020. 6. 2. 19:01
문제 : https://www.acmicpc.net/problem/16958 16958번: 텔레포트 2차원 평면 위에 N개의 도시가 있다. 일부 도시는 특별한 도시이다. (r1, c1)에 있는 도시에서 (r2, c2)에 있는 도시로 가는 이동 시간은 |r1 - r2| + |c1 - c2|와 같다. 만약, 두 도시가 특별한 도시라면, 텔 www.acmicpc.net 풀이 : 우선 2차원 행렬인 dist를 통해 A와 B의 거리를 계산해 놓는다. 그리고 직접 가는 방법 A -> B에 값을 구한다. 이때 A와 B가 둘 다 특별한 도시라면 T로 갱신할 수 있는지 체크해주어야 한다. 이제 더 작아질 수 경우는 A,B에 가장 가까운 곳을 방문해서 T를 이용해 가는 방법이다. 해당 경우가 더 작아지면 갱신해주게 된다...