주간 문제풀이 08 (BOJ 2325 / 8112 / 5916)

BOJ 2325 - 개코전쟁 (P5)

문제: 양방향 그래프가 주어지고, 이 그래프에서 1번 정점에서 N번 정점으로의 최단거리가 최대가 되도록 도로 하나를 파괴했을 때의 최단경로를 구하자. N <= 1000

풀이:

어떤 도로 하나를 파괴해야 한다면, 그 도로는 반드시 최단경로 위의 도로여야 한다. 그렇지 않다면 최단경로가 변하지 않기 때문이다.

그러면 우리는 1 -> N까지의 일반적인 최단경로를 찾고, 이 최단경로 위의 간선을 하나씩 뺀 상태에서 최단경로를 구한 후에 그 중 가장 큰 최단경로를 출력하면 문제를 풀 수 있다.

 

코드: http://boj.kr/210a1d3ec1d04851a8b1059749d6dae9

---

이렇게 풀면 다익스트라를 최대 N번 돌리고, 다익스트라의 시간복잡도가 약 M + NlogM이기 때문에, 곱하면 O(NM)의 시간복잡도로 시간초과가 난다고 생각할 수 있다. 다만 이 문제는 시간초과가 나지 않고 백준에서 100ms 내로 풀이가 돌고, 로컬에서 돌려본 맥스테케도 1초 정도에 돌았다. 아마 시간복잡도보다 꽤 많이 널널하게 도는 것 같다..

 

BOJ 8112 - 0과 1 - 2 (P4)

문졔: N이 주어지고, 0과 1로만 이루어진 수 중에서 N의 배수 중 가장 작은 수를 찾아야 한다.

풀이:

답이 되는 수의 첫 번째 숫자는 1이어야 한다. 그러면 숫자 1에서 시작해서 그 뒤에 계속해서 0또는 1을 추가하는 방식을 생각해 보자. 이 때 숫자를 추가하면서, 해당 숫자들로 이루어진 수 전체는 너무 크더라도, 해당 수의 mod N값은 유지할 수 있다. (0을 추가하면 *10, 1을 추가하면 *10+1이니까)

이 점을 이용해서 해당 문제를 그래프 탐색 문제로 변환할 수 있다. 구체적으로는, 노드 N개를 만들어서 i번째 노드가 mod N = i 인 상태를 표시하도록 만든다. 가장 처음에 "1" 로만 시작할 때는 1번째 노드에서 시작하는 셈이고, 여기서 모든 노드마다 밖으로 나가는 간선이 2개가 있고(하나는 0 추가 간선, 하나는 1 추가 간선), 이런 그래프에서 0번째 노드로 가는 최단경로가 문제가 원하는 답이 된다. 가장 작은 수를 구해야 하는 요구사항은, 0 간선을 1 간선보다 먼저 탐색하면 된다.

 

아래 그림은 N = 17인 케이스에서 답 "11101"을 나타내는 최단경로를 보여준다.

코드: http://boj.kr/823de6e5f6c042eaad168c010867bd90

BOJ 5916 - 농장 관리(P2)

문제: 트리가 주어지고, P와 Q 두 가지 쿼리를 처리한다. P u v쿼리는 u번 농장과 v번 농장 사이의 경로에 존재하는 모든 도로에 +1, Q u v쿼리는 u-v 도로 위의 숫자를 출력한다.

풀이:

Heavy Light Decomposition으로 풀 수 있다.

- P쿼리는 HLD를 통해 주어진 경로를 logN개로 분할하고, 각 logN개의 경로에 대해서 segment tree 상에서 range update를 수행해주는 식으로 log^2(N) 에 수행할 수 있다.

- Q쿼리는 segment tree상에서 특정 위치의 숫자를 쿼리하는 방식으로 풀 수 있다.

 

HLD 구현은 https://cp-algorithms.com/graph/hld.html 를 참고했고, Segment Tree 구현은 https://codeforces.com/blog/entry/18051 를 참고했다.

코드: https://www.acmicpc.net/source/share/3687515f0d434ebab8a34d951e67faa3