다익스트라 문제 모음

13308 주유소

https://www.acmicpc.net/problem/13308

 

각 도로의 길이와 각 노드의 주유 비용이 주어질 때, 1번노드에서 N번 노드까지 최소비용으로 

도착해야 하는 문제이다. 

이차원 dist 배열로 각 시점에서의 최소 주유 비용과 현재 노드 번호를 인덱스로 하여 값을 저장한다.

이를 통해 최소 주유 비용을 기억하면서, 다음으로 넘어갈 때마다 부족한 만큼의 양을 최소 주유비용 만큼 더해주면 된다.

 

즉, 미래를 대비해 미리 주유해놓을 시점을 찾는 것이 아니라 최소 비용을 기억하여 필요할 때만 채우면 되는 것이다.

 

 

1162 도로포장

https://www.acmicpc.net/problem/1162

1~N번까지의 도시가 있을 때 각 도시를 잇는 도로의 그 길이가 주어진다.

1번 도시에서 N번 도시까지 가는 비용이 최소가 되도록 K개의 도로를 포장하여 그 길이를 0으로 만들 수 있다.

K개의 도로를 포장했을 때 최단거리를 구해야 하는 문제이다. (1 <= N <= 10000) (1 <= K <= 20)

 

다익스트라를 몰랐던 당시에 도전했던 문제라 처음에는 순수 dp로 ac를 받으려 하다가 눈물나게 얻어터졌다.

dp[현재 도시][포장한 도로의 개수] 로 정의하여 

각 도로를 시작점을 기준으로 정렬한 다음에 하나씩 도로를 지워나가며 풀려고 했는데...

당연히 실패했다. 논리 자체도 빈약했을 뿐더러 정렬된 구간이 서로 이어져있다는 보장이 전혀 없었다.

 

올바른 다익스트라 풀이는 d[현재 도시][현재까지 포장한 도로의 수] 로 설정한 다음, 

거리를 반영하여 다음 도시로 갈 때, 도로를 포장하지 않았을 경우보다 누적 거리가 개선된다면 도로를 포장하는 방식을 사용하여,

마지막 도시에 도착했을 때, 포장한 개수에 따른 최솟값을 구하면 된다.

 

 

10217 KCM Travel 

https://www.acmicpc.net/problem/10217

 

각 길의 비용과 걸리는 시간이 주어질 때, 주어지는 비용 M 내에서 도착지에 도착하는데 걸리는 최소 시간을 구해야 하는 문제이다.

거리와 비용을 인덱스로 하는 이차원 dist 배열을 앞선 문제와 마찬가지로 거리가 개선되는 경우에만 최소힙에 push 하며 비용이 M이상인 경우에는 제외해주면 된다.

하지만 이것만으로는 시간초과가 발생하는데, 이때에는 도로를 가중치를 기준으로 정렬해주면 상수최적화가 가능하다. 

 

 

 

34120 무궁화 꽃이 피었습니다

https://www.acmicpc.net/problem/34120

 

한국이가 눈을 감고 뜨는 주기가 주어지고, 창문이 있는 건물, 없는 건물의 번호, 각 도로를 걷는데 걸리는 시간 등이 주어졌을 때, 

한국이에게 걸리지 않고서 1번 건물에서 N번 건물까지 가는데 걸리는 시간을 구해야 하는 문제이다. 

 

우선 첫번째 풀이는 여러번의 시도 끝에 AC를 받은 약간 지저분한? 풀이이다.

 

현재 창문이 있는 건물에 있다면 한국이는 현재 눈을 감고 있는 상태일 것이다.

때문에, 한국이가 다시 눈을 뜨기 전에 최대한 다른 건물로 피해야 한다.

창문이 있기 때문에 눈을 다시 뜨기 전까지 남은 시간이 다른 모든 도로를 걷는데에 부족하다면 해당 경로는 불가능해진다.

 

두번째 경우로 현재 창문이 없는 건물에 있다면 많은 가능성이 생긴다.

창문이 없기 때문에, 꼭 필요한 상황이 아니더라도 나중을 위해 게임 한턴(눈을 뜨고 감고)을 버틸 수 있다.

그렇다면 아래 3가지 경우가 생겨난다.

 

1. 다시 눈을 뜨기까지의 시간이 촉박하여 건물 내에서 한턴 버티는 경우

2. 다시 눈을 뜨기까지의 시간이 충분함에도 다른 건물로 가지 않고 건물 내에서 한턴 버티는 경우

3. 다시 눈을 뜨기까지의 시간이 충분하여 다른 건물로 이동하는 경우

 

위와 같이 3가지 경우가 가능한데, 건물 내에서 한턴 몸을 숨기는 경우는 단기적으로는 최단경로가 아니지만, 눈을 뜨고 있을 시점에 창문이 있는 건물 또는 도로 위에 있을 경우에는 해당 경로가 불가능해진다는 변수 때문에 마지막에는 최단경로, 또는 유일한 경로가 될 수 있다.

 

때문에, 다익스트라를 한번만 돌려서  모든 경우가 반영되도록 풀기 위해서는 상태 정의가 필요하다.

창문이 없는 건물에서 몸을 숨긴 횟수를 상태로 하여 이차원 dist 배열을 만든다.

그리고 위 논리에 따라 몸을 숨기는 경우와 숨기지 않는 경우, 창문이 없어서 바로 다음으로 가는 경우 모두를 반영하도록 다익스트라를 돌리면 된다.

 

하지만 여기서 한번 더 까다로운 변수가 생기는데, 몸을 숨기는 횟수 최대치를 건물의 최대치 2000으로 설정했을 때 이유는 모르겠지만 부분점수를 받는다. 상태 정의 배열 제한을 2000에서 도로의 개수 제한인 4000으로 바꿨을 때 만점을 받을 수 있었다.

 

더 깔끔한 풀이는 다익을 두번 돌리는 풀이라는데, 잘 모르겠다. 나중에 다시 풀어봐야겠다.