23.05.29 - 23.05.31 공부(그래프 파트 1 : 플로이드)

아직 남은 대회 후기가 몇 개 있긴 한데, 아무래도 조금 밀릴 듯 싶다.. 글 한 편 적는 데에도 적지 않은 노력이 필요하다는 것을 알아버렸기 때문에.. 
 
종만북에서 그래프 파트를 파고 있는 중이다. 플로이드, 데이크스트라, 벨만-포드, 아직 조금 부족하지만 플로우까지 계속해서 반복 공부하고 있다. 배운 내용을 문제에 적용해볼 필요를 느껴서 오랜만에 바킹독 문제집을 정주행 해보기로 했다. 첫 파트는 [플로이드 알고리즘]이다.

https://www.acmicpc.net/workbook/view/10318

1) 13168 내일로 여행 - UCPC를 위해 아껴놓기로..
2) 13314 플로이드에 오타가? - 폰에서 cpp 파일을 열기 어려워서..

1. 백준 17182번 - 우주 탐사선

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

17182번: 우주 탐사선

계속해서 최단 경로로만 탐색하는 그리디는 성립하지 않는다. 최단 경로의 집합은 아니지만, 그 합이 최소가 되는 경우가 존재할 수 있기 때문이다. 따라서 행성 탐사 순서가 중요하다.

$N$이 10이하로 굉장히 작기 때문에 백트래킹을 이용한 완전탐색이 가능하다. 물론 임의의 행성 $a$, $b$ 간 탐색 시간은 최소로 구해놓은 뒤 완전탐색을 진행해야 한다. (굳이 최소로 하지 않고 탐색하여 손해볼 필요는 없기 때문.) 이때 플로이드 알고리즘을 사용하면 된다.

2. 백준 11562번 - 백양로 브레이크

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

11562번: 백양로 브레이크

재미있는 문제. 입력된 도로의 종류에 따라 도로의 가중치를 달리하면 된다. 단방향이라면 역방향 간선을 추가한 뒤 그 간선에 가중치 1을 부여한다. 만약 그 간선이 양방향 도로가 필요한 곳이라면, 양방향으로 바꾸어야 할 도로 개수에 1을 더하는 효과를 낼 수 있기 때문이다.

이렇게 모델링을 한 뒤 플로이드 알고리즘을 진행한다.

3. 백준 1719번 - 택배

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

1719번: 택배

은근히 까다롭게 느껴진 문제. 우선 플로이드 알고리즘을 통해 최단거리를 구하는 기본 골조에는 변함이 없다. 만약 어떤 경유점을 지났을 때 최단거리가 갱신된다면 어떤 두 정점 $u$, $v$ 간 최단거리 경로에 그 경유점이 포함된다는 것을 의미한다. 이때, 그 경유점과 $u$가 연결되어 있다면 그 경유점을 답으로 사용해도 된다. 만약 그렇지 않다면, $u$와 그 경유점을 잇는 최단거리 경로 중 $u$와 이어진 정점이 있는지를 확인하며 답을 갱신하도록 한다. connected가 서로 이어져있는지를, stage가 최단 거리를, result가 최종 답을 출력하는 행렬임을 나타낼 때, 코드는 다음과 같이 구성해볼 수 있다.

for(int k = 1; k <= n; k++)
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(stage[i][j] >= stage[i][k] + stage[k][j])
            {
                stage[i][j] = stage[i][k] + stage[k][j];

                if(connected[i][result[i][k]])
                    result[i][j] = result[i][k];
            }

 
 
 
 

4. 백준 23286번 - 허들 넘기

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

23286번: 허들 넘기

여기 있는 8개의 문제 중 가장 쉬운 문제가 아닐까 하는 생각이 든다. 플로이드 알고리즘에서 구하고자 하는 것을 살짝 바꿔주면 된다. 경유점 $k$를 차례대로 돌면서, 그 경유점을 경유했을 때 최대가 되는 높이를 구하고, 그것이 최소가 될 수 있는지를 살펴본다.

따라서 점화식은,
$stage[i][j] = min(stage[i][j], max(stage[i][k], stage[k][j]))$

5. 백준 1507번 - 궁금한 민호

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

1507번: 궁금한 민호

우선 모든 정점이 서로 연결되어있다고 하자. 어떤 경유점을 통하여 최단거리를 뽑아낼 수 있다면 그 도로는 필요가 없으니 지워버린다. 자세하게 어떤 얘기냐 하면..

$a$와 $b$ 사이의 거리가 어떤 경유점 $k$를 통하여 $dist[a][b] = dist[a][k] + dist[k][b]$를 만족시킬 수 있다면, $a$와 $b$ 사이의 도로는 필요없음을 알 수 있다. 이때 $k$는 $a$와 $b$가 아닌 수 중 하나하나 순회하면서 알아보는데, 하나의 경유점만으로도 충분한 이유는, 행렬에 나와 있는 최단거리들은 플로이드 알고리즘 상에서 이미 모든 경유점을 순회하였기 때문이다. 즉, 경유점 하나만 골라도 모든 경유점을 돌며 갱신한 것과 같은 효과를 낼 수 있는 것이다.

이상에서 행렬을 만족시킬 수 없는 조건은 $dist[a][b] > dist[a][k] + dist[k][b]$임을 알 수 있다. 더 짧은 최단거리 방식이 존재함에도, 행렬에 그러한 값이 나타나 있지 않는 것은 불가능하다.


 
 

6. 백준 13141번 - Ignition

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

13141번: Ignition

플레에 쫄지 말고 차근차근 관찰한 뒤 끄적거리다보면 어느 순간 풀리는 문제.  임의의 시작 정점 $u$를 기준으로 어떤 정점 $v$에 불이 처음 붙는 시기는 $u$에서 $v$까지의 최단 거리를 이동했을 때임을 알 수 있다. 이때 $u$에서 $v$를 잇는 어떤 간선이 불타지 못하고 여전히 남아있을 수도 있다. $v$에 처음으로 불이 붙은 시점에서 이 간선의 길이는 얼마일까? 처음 간선의 길이에서 $v$까지의 최단 거리를 뺀 값일 것이다. 이제 이 간선은 남은 간선의 길이를 반으로 나눈 시간 후에 불타 없어질 것이다.

이 논의를 확장시켜보자. 시작 정점 $u$를 기준으로 어떤 임의의 두 정점 $v_1$, $v_2$까지의 최단거리(최단 시간)를 각각 $d_1$, $d_2$라고 하자. 또, $v_1$, $v_2$를 잇는 어떤 간선의 길이를 $t$라고 하자. 그렇다면 그 간선이 불타 없어지는 시간은 $max(d_1, d_2) + \frac{t-|d_1-d_2|}{2}$로 정리할 수 있다.

모든 쌍의 최단거리를 플로이드 알고리즘으로 구해놓은 뒤, 시작 정점을 차례대로 정해놓은 뒤 위 식이 최소가 되는 값을 찾아본다.

7. 백준 1602번 - 도망자 원숭이

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

1602번: 도망자 원숭이

종만북의 [음주 운전 단속] 문제와 매우매우 유사한 문제. 한 가지 다른 점이 있다면 이 문제는 시작점과 도착점 또한 고려하여야 한다는 점이다.

플로이드 알고리즘의 핵심은 '경유점 집합을 차례차례 늘려나간다'는 점이다. 단순히 최단경로만을 구하고자 할 때에는 편의상 $k$(가장 바깥 반복문)를 1부터 $n$까지 순회하는 방식으로 구현했었지만 이런 문제에서는 경유점을 일정 기준에 맞추어 순회해야 한다.

그 기준은 무엇으로 정해야 할까? 두 가지를 생각해볼 수 있다.

1. 괴롭힘 시간의 내림차순
2. 괴롭힘 시간의 오름차순

1. 의 방식으로 진행한다면 경유점 집합을 늘려갈 때, 지금까지의 괴롭힘 시간의 최댓값을 알아내기가 어렵다. 반면 2.의 방식으로 진행한다면, 경유점이 현재로서는 괴롭힘 시간의 최댓값(아직 한 단계가 더 남았긴 하지만)이므로 답을 정확하게 구해낼 수 있다. 다시 말해, 1.의 방식은 괴롭힘 시간의 하한을, 2.의 방식은 괴롭힘 시간의 상한을 구하는 방식으로 갈리는데, 이 문제에서는 2.를 따라가야 함을 알 수 있다.

물론 이 문제에서는 출발점과 도착점 또한 포함해서 생각해야 하므로, 매 경유점 집합을 늘려나갈 때마다 출발점의 괴롭힘 시간, 도착점의 괴롭힘 시간, 경유점의 괴롭힘 시간 중 최댓값을 구한 뒤 결과값을 갱신해야 한다.

8. 백준 23258번 - 밤편지

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

23258번: 밤편지

$2^X$, $2^C$가 낯설게 다가와서 겁먹긴 했지만 갈피만 잡으면 의외로 쉬운 문제.

$X$번 집만이 $2^X$방울의 이슬이 있으므로 $2^C$방울을 넘기지 않으러면 번호가 $C$ 이상인 집을 들리지만 않으면 된다. 따라서 경유점 집합을 1부터 $N$까지 늘려가며 최단 거리를 구하면 된다.

단, 쿼리는 $C$가 순차적으로 주어져 있지 않으므로 '오프라인 쿼리'를 활용해볼 수 있다. $C$를 기준으로 쿼리를 정렬한 다음, 현재의 경유점+1이 어떤 쿼리의 $C$와 같다면, 그때의 $s$번 집과 $e$번 집 간의 최단 거리를 출력한다. (물론 원래의 쿼리 순서에 주의해야 한다.)