1948. 임계경로

Notice

Recent Posts

Recent Comments

Link

« 2025/09 »
일	월	화	수	목	금	토
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30

Tags more

Archives

Today

Total

관리 메뉴

이동식 저장소

1948. 임계경로 본문

Problem Solving/BOJ

1948. 임계경로

해스끼 2020. 12. 14. 20:40

1948번: 임계경로

첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의

www.acmicpc.net

문제가 조금 난해하게 쓰여 있지만, 사실 최장 경로 문제이다. 즉 최장 경로의 길이를 구하고, 최장 경로에 포함되는 간선의 수를 구하는 문제이다.

맞왜틀 1 (펼치기)

최장 경로가 여러 개 있을 경우, 각 경로가 포함하는 간선을 모두 세어야 한다. 예를 들어 다음과 같은 경우가 있다.

일반적인 그래프에서의 최장 경로 문제는 NP-complete이다. 하지만 이 문제에서는 그래프가 유향이므로 전형적인 재귀 DP를 이용하여 문제를 해결할 수 있다. $d [i] <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>d</mi><mo stretchy="false">[</mo><mi>i</mi><mo stretchy="false">]</mo></math>$ 를 $i <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi></math>$ 번 정점에서 도착 정점까지의 최장 경로의 길이라고 할 때, $i <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi></math>$ 번 정점과 연결된 모든 정점 $j <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>j</mi></math>$ 에 대해 $d [i] = max (d [j] + c o s t [i] [j]) <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>d</mi><mo stretchy="false">[</mo><mi>i</mi><mo stretchy="false">]</mo><mo>=</mo><mo data-mjx-texclass="OP" movablelimits="true">max</mo><mo stretchy="false">(</mo><mi>d</mi><mo stretchy="false">[</mo><mi>j</mi><mo stretchy="false">]</mo><mo>+</mo><mi>c</mi><mi>o</mi><mi>s</mi><mi>t</mi><mo stretchy="false">[</mo><mi>i</mi><mo stretchy="false">]</mo><mo stretchy="false">[</mo><mi>j</mi><mo stretchy="false">]</mo><mo stretchy="false">)</mo></math>$ 이다.

그런데 문제에서 추가로 간선의 개수까지 요구하고 있고, 맞왜틀 1 때문에 어떤 식으로든 최장 경로를 추적할 필요가 있다. 나는 최장 경로에서 $i <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi></math>$ 번 정점 이후의 정점을 $t r a c k [i] <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>t</mi><mi>r</mi><mi>a</mi><mi>c</mi><mi>k</mi><mo stretchy="false">[</mo><mi>i</mi><mo stretchy="false">]</mo></math>$ 에 저장하고, 나중에 따로 BFS하는 방법으로 간선을 셌다.

맞왜틀 2 (펼치기)

맞왜틀 1의 입력처럼 같은 간선이 여러 개 주어질 수도 있고, 하필 그러한 간선이 최장 경로에 포함될 수도 있다. 이럴 때 일반적인 BFS로는 정답을 구할 수 없다.

큐에 넣는 양식(방문 처리 등)은 그대로 하되, 큐에서 꺼내는 모든 정점

c u r <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>c</mi><mi>u</mi><mi>r</mi></math>

에 대해

t r a c k [c u r] <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>t</mi><mi>r</mi><mi>a</mi><mi>c</mi><mi>k</mi><mo stretchy="false">[</mo><mi>c</mi><mi>u</mi><mi>r</mi><mo stretchy="false">]</mo></math>

의 크기의 합을 반환해야 한다.

플레5 치곤 쉬운 문제.

저작자표시 비영리 변경금지 (새창열림)

'Problem Solving > BOJ' 카테고리의 다른 글

1561. 놀이 공원 (1)	2020.12.24
5214. 환승 (2)	2020.12.21
3020. 개똥벌레 (0)	2020.12.14
3000. 직각삼각형 (0)	2020.11.20
2610. 회의준비 (0)	2020.11.13