이게 어떤 원리, 알고리즘으로 해결이 되는 건지 아시는 분 계신가요?

Question

if (dist[a][b] <&#61; x || dist[c][d] <&#61; y) {yes &#61; true;} else {yes &#61; (dist[a][c] &#43; dist[b][d] &#43; 2 <&#61; x &#43; y) ||(dist[a][d] &#43; dist[b][c] &#43; 2 <&#61; x &#43; y);}문제의 답을 보니 각 정점 사이의 최단 거리를 전부 구하고 가능 여부를 해당 조건문으로 판단하던데 왜 이 조건문으로 판단할 수 있는건지 아무리 생각해도 이해가 안 됩니다.

yeori · Answer

두 건물 B, T가 아무리 멀리 떨어져 있어도, 무빙워크를 딱 1개만 놓으면 두 건물 사이를 1분 안에 갈 수 있답니다.건물 (A, B)와 건물 (C, D) 가 주어졌는데, AB는 x 분 안에, CD는 y분 안에 가고 싶데요.그런데 AB 사이의 최단 거리가 이미 x분 이하이면 무빙워크를 CD에 놓을 여지가 있으니 조건을 충족하죠.반대의 경우도 마찬가지구요.그런데 둘 다 조건을 충족하지 못할때가 문제네요(AB와 CD 모두 x분, y분이 넘음)이럴 경우 무빙워크를 AB에 놓거나, 또는 CD에 놓아서 둘 중 한쪽이라도 조건을 만족시켜놓고 다른 한쪽의 시간을 재계산 해보겠다는겁니다.아래와 같이 AB에 무빙워크를 두면 x분 초과하던 구간이 1분이 되네요.A ++ B C ---D 그러면 이제 CD를 y분 안에 갈 수 있는지 보겠다는겁니다.C에서D로 가는 구간이 3개가 있네요.C~A~D 이 구간은 CD보다 반드시 오래 걸리네요. 왜냐하면 이미 CD가 최단거리니까 다른데 거쳐가면 더 올래걸림C~B~D: 마찬가지로 얘도 원래 CD보다 더 오래 걸림C~A~B~D: 이 구간은 가능성이 있습니다. AB가 1이기때문에 CA+AB + BD 를 계산해볼만하네요.C~B~A~D: 3번과 마찬가지인데 교차해서 시도해봐야 함. CB + BA + AD를 봐야 함.이걸 코드에서 dist[a][c] + dist[b][d] + 2 라고 거지같이 표현한겁니다.알아보기 쉽게 고치면1 + ( CA + 1 + BD ) // 3번 케이스라고 쓰면 좋죠. 첫번째 1은 무빙워크로 이동한 AB 거리이고 괄호 안은 CABD 구간입니다.4번 케이스도 1 + ( CB + 1 + AD )그런데 이거 말고 두 구간 사이에 다리를 놓는 케이스도 있습니다.AC 또는 BD에 놓을 수도 있음...A --- B + + C ---D 기존의 AB CD는 모두 x, y분을 초과하니까, 이제 둘다 AC를 반드시 지나서 경로를 계산해봐야 합니다.AB는 AC + CB로,CD는 CA + AD로,여기서 AC = CA = 1 이니까 정리하면 (1 + BC) + (1 + AD)..가 됨다리를 BD에 두게 되면 (AD + 1) + (CB + 1)..가 됨.모든 케이스를 다 보면 결국 공식은 똑같죠.

이게 어떤 원리, 알고리즘으로 해결이 되는 건지 아시는 분 계신가요?

1개의 답변

Q&A 목록