"use strict"; const {Fragment: _Fragment, jsx: _jsx, jsxs: _jsxs} = arguments[0]; const {useMDXComponents: _provideComponents} = arguments[0]; function _createMdxContent(props) { const _components = { a: "a", annotation: "annotation", code: "code", figure: "figure", h2: "h2", img: "img", li: "li", math: "math", mi: "mi", mo: "mo", mrow: "mrow", p: "p", pre: "pre", semantics: "semantics", span: "span", ul: "ul", ..._provideComponents(), ...props.components }; return _jsxs(_Fragment, { children: [_jsx(_components.p, { children: _jsx(_components.a, { href: "https://www.acmicpc.net/problem/2611", children: "문제 링크" }) }), "\n", _jsx(_components.h2, { children: "문제" }), "\n", _jsx(_components.p, { children: "자동차 경주로는 <그림 1>의 예와 같이 표현된다. 화살표는 각 지점을 잇는 도로를 의미하며 모든 도로는 일방통행 도로로 화살표 방향으로만 움직일 수 있다." }), "\n", _jsx(_components.p, { children: _jsx(_components.img, { src: "/generated/posts/algorithm/boj-2611/assets/img1.jpg", alt: "" }) }), "\n", _jsx(_components.p, { children: "자동차 경주의 코스는 1번 지점에서 출발하여 다시 1번 지점으로 되돌아오는 것이다. 단, 중간에는 1번 지점을 지나서는 안 된다. 경주로는 1번 지점을 제외한 어느 지점에서 출발하여도 1번 지점을 지나가지 않고서는 같은 지점으로 돌아올 수 없도록 되어 있다. 또한 1번 지점에서 다른 모든 지점으로 갈 수 있고, 다른 모든 지점에서 1번 지점으로 갈 수 있다." }), "\n", _jsx(_components.p, { children: "각 도로에는 <그림 2>의 예와 같이 그 도로를 지날 때 얻는 점수가 있다." }), "\n", _jsx(_components.p, { children: _jsx(_components.img, { src: "/generated/posts/algorithm/boj-2611/assets/img2.jpg", alt: "" }) }), "\n", _jsx(_components.p, { children: "1번 지점에서 출발하여 가장 많은 점수를 얻어 다시 1번 지점으로 돌아오는 팀이 우승을 하게 된다. 가장 많은 점수를 얻어 1번 지점으로 돌아오는 경로를 찾아 그 얻는 점수와 경로를 출력하는 프로그램을 작성하시오." }), "\n", _jsx(_components.h2, { children: "입력" }), "\n", _jsx(_components.p, { children: "첫째 줄에는 지점의 개수 N이 주어진다. 각 지점에는 1부터 N까지의 서로 다른 번호가 부여된다. 둘째 줄에는 도로의 개수 M이 주어진다. 이어 M개의 줄에는 p ,q ,r의 형식으로 도로의 정보가 주어지는데 이는 p번 지점부터 q번 지점으로 갈 수 있는 도로가 있고 그 도로에 부여된 점수가 r이라는 뜻이다. N은 1000이하의 자연수이고, p와 q는 1이상의 N이하의 자연수이며 r은 100이하의 자연수 이다. p와 q는 같지 않다." }), "\n", _jsx(_components.h2, { children: "출력" }), "\n", _jsx(_components.p, { children: "가장 많은 점수를 얻은 경로를 찾아, 첫째 줄에는 그 얻는 점수를 출력하고 둘째 줄에는 그 경로를 출력한다. 경로를 출력할 때는 지나는 지점들의 번호를 사이에 한 칸의 공백을 두어 출력한다. 출력하는 경로는 반드시 1번 지점에서 시작하여 1번 지점으로 끝나야 한다. 만약 같은 점수를 얻는 경로가 둘 이상일 경우 그 중 하나만 출력하면 된다." }), "\n", _jsx(_components.h2, { children: "풀이" }), "\n", _jsx(_components.p, { children: "문제 구조상 1번으로 돌아오는 경로를 제외하면 DAG처럼 처리할 수 있어서, 위상 정렬 기반 DP가 가능하다." }), "\n", _jsxs(_components.p, { children: ["코드에서는 진입차수 ", _jsx(_components.code, { children: "degree[]" }), "를 이용해 1번에서 시작하는 위상 순회를 하며, 각 정점까지의 최대 점수 ", _jsx(_components.code, { children: "dp[]" }), "와 이전 정점 ", _jsx(_components.code, { children: "parents[]" }), "를 갱신한다. 어떤 간선을 통해 왔을 때 점수가 더 크면 그 간선이 현재 최적 경로가 된다."] }), "\n", _jsx(_components.p, { children: "여기서 중요한 구현 포인트는 1번 정점으로 들어오는 간선은 진입차수 계산에서 제외한다는 점이다. 그래야 출발점인 1번을 기준으로 나머지 구간을 DAG처럼 밀어낼 수 있다. 그렇지 않으면 사이클 때문에 일반적인 위상 정렬이 깨진다." }), "\n", _jsxs(_components.p, { children: ["최대 점수만 구하면 끝나는 것이 아니라 실제 경로도 출력해야 하므로, 점수가 갱신될 때마다 ", _jsx(_components.code, { children: "parents[next] = cur" }), "를 함께 기록한다. 마지막에는 ", _jsx(_components.code, { children: "parents[]" }), "를 거꾸로 따라가면서 1번에서 1번으로 돌아오는 최적 경로를 복원하면 된다."] }), "\n", _jsx(_components.h2, { children: "코드" }), "\n", _jsx(_components.figure, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.pre, { style: { backgroundColor: "#2e3440ff", color: "#d8dee9ff" }, tabIndex: "0", "data-language": "java", "data-theme": "nord", children: _jsxs(_components.code, { "data-language": "java", "data-theme": "nord", style: { display: "grid" }, children: [_jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: "import" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: " java" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: "io" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "*;" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: "import" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: " java" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: "util" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "*;" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: "import" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: " java" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: "util" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: "stream" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: "Collectors" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: "public" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " class" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: " Main" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " static" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " class" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: " Edge" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " to" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " weight" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#88C0D0" }, children: " Edge" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " to" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " weight" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " this" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "to" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " to" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " this" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "weight" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " weight" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " static" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[]" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " degree" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " static" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: " ArrayList" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "<" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: "Edge" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ">[]" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " adj" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " static" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " N" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " public" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " static" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " void" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " main" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: "String" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[]" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " args" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " throws" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: " IOException" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#8FBCBB" }, children: " BufferedReader" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " br" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " new" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " BufferedReader" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "new" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " InputStreamReader" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "System" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "in" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "))" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " N " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " Integer" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "parseInt" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "br" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "readLine" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "())" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " M" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " Integer" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "parseInt" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "br" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "readLine" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "())" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " degree " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " new" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "N " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "+" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 1" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " adj " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " new" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: " ArrayList" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "N " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "+" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 1" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " for" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " i" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 1" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " i " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "<=" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " N" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " i" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "++" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " adj" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "i" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " new" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: " ArrayList" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "<>()" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " while" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "M" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "--" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " >" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 0" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#8FBCBB" }, children: " StringTokenizer" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " st" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " new" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " StringTokenizer" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "br" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "readLine" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "())" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " p" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " Integer" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "parseInt" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "st" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "nextToken" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "())" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " q" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " Integer" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "parseInt" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "st" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "nextToken" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "())" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " r" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " Integer" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "parseInt" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "st" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "nextToken" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "())" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " adj" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "p" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "add" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "new" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " Edge" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "q" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " r" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "))" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " if" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "q " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "!=" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 1" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " degree" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "q" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "++;" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9" }, children: " System" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "out" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "println" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "solve" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "())" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " static" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: " String" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " solve" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "()" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#8FBCBB" }, children: " Queue" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "<" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: "Integer" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ">" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " q" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " new" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: " ArrayDeque" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "<>()" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9" }, children: " q" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "offer" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: "1" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[]" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " dp" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " new" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "N " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "+" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 1" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[]" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " parents" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " new" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "N " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "+" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 1" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " while" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "!" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "q" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "isEmpty" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "())" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " cur" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " q" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "poll" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "()" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " for" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: "Edge" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " edge" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " :" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " adj" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "cur" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "])" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " next" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " edge" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "to" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " weight" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " edge" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "weight" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " if" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "dp" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "next" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " <" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " dp" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "cur" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " +" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " weight" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " dp" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "next" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " dp" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "cur" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " +" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " weight" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " parents" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "next" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " cur" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " if" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "next " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "!=" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 1" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " degree" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "next" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "--;" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " if" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "degree" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "next" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " ==" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 0" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9" }, children: " q" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "offer" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "next" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#8FBCBB" }, children: " ArrayDeque" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "<" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: "Integer" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ">" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " result" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " new" }), _jsx(_components.span, { style: { color: "#8FBCBB" }, children: " ArrayDeque" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "<>()" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " cur" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " =" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 1" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9" }, children: " result" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "addFirst" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: "1" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " while" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "parents" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "cur" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " !=" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 1" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " cur " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " parents" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "cur" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9" }, children: " result" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "addFirst" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "cur" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " }" }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9" }, children: " result" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "addFirst" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: "1" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " return" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " String" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "valueOf" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "dp" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: "1" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "])" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " +" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " '" }), _jsx(_components.span, { style: { color: "#EBCB8B" }, children: "\\n" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "'" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " +" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9" }, children: " result" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "stream" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "()" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#ECEFF4" }, children: " ." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "map" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "String" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "::" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "valueOf" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#ECEFF4" }, children: " ." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "collect" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "Collectors" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "joining" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "\"" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " \"" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "))" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "}" }) })] }) }) }), "\n", _jsx(_components.h2, { children: "복잡도" }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["시간 복잡도: ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "N" }), _jsx(_components.mo, { children: "+" }), _jsx(_components.mi, { children: "M" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "O(N + M)" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.109em" }, children: "N" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.109em" }, children: "M" }), _jsx(_components.span, { className: "mclose", children: ")" })] })] })] })] }), "\n", _jsxs(_components.li, { children: ["공간 복잡도: ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "N" }), _jsx(_components.mo, { children: "+" }), _jsx(_components.mi, { children: "M" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "O(N + M)" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.109em" }, children: "N" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.109em" }, children: "M" }), _jsx(_components.span, { className: "mclose", children: ")" })] })] })] })] }), "\n"] }), "\n", _jsx(_components.h2, { children: "마무리" }), "\n", _jsx(_components.p, { children: "최대 점수 경로 문제지만, 위상 정렬이 가능하다는 점을 이용하면 훨씬 단순해진다. 점수 DP와 부모 추적을 같이 하면 경로 복원도 어렵지 않다." }), "\n", _jsx(_components.p, { children: _jsx(_components.img, { src: "/generated/posts/algorithm/boj-2611/assets/1.png", alt: "" }) })] }); } function MDXContent(props = {}) { const {wrapper: MDXLayout} = { ..._provideComponents(), ...props.components }; return MDXLayout ? _jsx(MDXLayout, { ...props, children: _jsx(_createMdxContent, { ...props }) }) : _createMdxContent(props); } return { default: MDXContent };

BOJ 2611 - 자동차경주