BOJ 13911 집구하기

 

문제 링크 : https://www.acmicpc.net/problem/13911

13911번: 집 구하기

 

어떤 지점을 중심으로 가장 가까운 맥도날드나 스타벅스를 구하라면 평범한 최단 경로 문제이겠으나,

정점들 중 거리의 합이 최소가 되어야 하므로 각 정점에서 맥도날드 스타벅스까지의 최단 경로를 구하기는 곤란하다. (정점이 너무 많다.)

 

그래서 출발 정점을 맥도날드나 스타벅스로 두고 해결해야 할 듯하다. (이것도 많은데?)

가장 가까운 소방서, 경찰서까지의 거리의 합이 최소가 되는 등등의 조건으로 비슷한 문제를 여러번 본 것 같다.

 

 

너비우선 탐색이나 다익스트라 알고리즘이 진행될 때 큐(혹은 우선순위 큐) 내부를 생각해보자. 

출발점에서 연결된 간선이 없거나 1 인 특수한 경우를 제외하면 큐 내부에는 대체로 여러 개의 정점에 관한 정보가 들어있게 된다.

큐나 우선순위 큐가 보장해 주는 것은 먼저 입력되었거나 비용(거리)이 작은 것이 먼저 튀어 나오게 된다는 것일 뿐.

처음의 정보가 어떤 의미를 가지고 있는지는 중요하지 않다.

 

어떤 지점(정점)에서 가장 가까운 맥도날드까지의 거리를 뒤집어서 생각해보자.

각각의 맥도날드에서 다른 사람들이 동시에 출발했을 때 가장 빨리 그 지점에 도착하는 사람이 누구냐는 문제가 된다.

따라서 각각의 맥도날드를 거리 0 으로 초기화하고 큐에 집어 넣었을 때, 가장 빨리 튀어 나오는 것으로 그 정점의 거리를 정하면 된다.

즉, 맥도날드에 해당되는 정점을 모두 큐에 집어 넣고 최단경로를 찾으면 한 번의 수행으로 원하는 결과를 얻는다.

 

스타벅스도 동일한 요령으로 취급하면 된다.

위 조건에서 보듯이 거리 제한(맥세권, 스세권)이 있으므로 거리를 구하다가 제한을 넘기면 탐색을 종료해도 문제가 없다.

 

 

코드의 마지막 부근의 다음 조건은 설명을 붙여둔다.

 

Cst[0][i]==0 의 의미는 그 지점에 맥도날드가 있으니 집이 아니라는 뜻.

Cst[0][i]>Mlim 은 가장 가까운 맥도날드까지의 거리가 원하는 제한을 넘었다는 뜻이다.

 

위의 코드에서 보면 우선순위 큐에서 빠져나온 지점의 거리가 제한을 넘기면 찾기를 종료했지만, 

정점들의 거리는 큐에서 나온 시점이 아니라 큐에 입력될 때 갱신됨을 상기하자.

그래서 거리가 제한을 넘었음에도 Inf 가 아닌 값으로 갱신되는 정점들은 여러 개 있을 것이다. 따라서

Cst[0][i]>Mlim 

인 정점들은 걸러야 한다.

그렇지 않으면 두 거리의 합산은 Mlim+Slim 보다 작지만 어느 하나의 제한을 만족하지 못하는 경우가 발생한다.