본문 바로가기

Dijkstra24

백준 20182 골목 대장 호석 - 효율성 1 Kotlin (다익스트라 + 이분 탐색) 문제 출처 : https://www.acmicpc.net/problem/20182 20182번: 골목 대장 호석 - 효율성 1 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net 문제 소싯적 호석이는 골목 대장의 삶을 살았다. 호석이가 살던 마을은 N 개의 교차로와 M 개의 골목이 있었다. 교차로의 번호는 1번부터 N 번까지로 표현한다. 골목은 서로 다른 두 교차로를 양방향으로 이어주며 임의의 두 교차로를 잇는 골목은 최대 한 개만 존재한다. 분신술을 쓰는 호석이는 모든 골목에 자신의 분신을 두었고, 골목마다 통과하는 사.. 2022. 5. 12.

백준 20168 골목 대장 호석 - 기능성 Kotlin (다익스트라 + 이분 탐색) 문제 출처 : https://www.acmicpc.net/problem/20168 20168번: 골목 대장 호석 - 기능성 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net 문제 소싯적 호석이는 골목 대장의 삶을 살았다. 호석이가 살던 마을은 N 개의 교차로와 M 개의 골목이 있었다. 교차로의 번호는 1번부터 N 번까지로 표현한다. 골목은 서로 다른 두 교차로를 양방향으로 이어주며 임의의 두 교차로를 잇는 골목은 최대 한 개만 존재한다. 분신술을 쓰는 호석이는 모든 골목에 자신의 분신을 두었고, 골목마다 통과하는 사람.. 2022. 5. 11.

백준 10217 KCM Travel Kotlin (다익스트라) 문제 출처: https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 문제 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세에 힘입어 구글 역시 대기업답게 비용 감축에 열을 내고 있었던 것이다. 초대장 내용에 의하면 구글은 찬민에게 최대 M원까지의 .. 2022. 5. 8.

백준 6087 레이저 통신 Kotlin (다익스트라) 문제 출처 : https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 문제 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다. 레이저는 C에서만 발사할 수 있.. 2022. 4. 26.

swea 1249. [S/W 문제해결 응용] 4일차 - 보급로 Java (다익스트라) 문제 출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com ※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다. 문제에 저런 멘트가 있어서 혹시나 문제가 될까봐 문제 내용은 긁어오지 않았습니다. 아마 복제하여 문제로 출제하는 것을 문제삼는 것 같고 이런 풀이 글에는 상관없을 것 같긴 한데 혹시나..! 문제도 올려도 되는지 아시는 분 있으면 댓글 달아주세요! 풀이 다익스트라 기본 문제이다. 다익스트라는 가중치가 다른 그래프에서.. 2022. 2. 19.

백준 22865 가장 먼 곳 Kotlin (다익스트라) 문제 출처 : https://www.acmicpc.net/problem/22865 22865번: 가장 먼 곳 $N$개의 땅 중에서 한 곳에 자취를 하려고 집을 알아보고 있다. 세 명의 친구 $A$, $B$, $C$가 있는데 이 친구들의 살고 있는 집으로부터 가장 먼 곳에 집을 구하려고 한다. 이때, 가장 먼 곳은 선택할 www.acmicpc.net 문제 N개의 땅 중에서 한 곳에 자취를 하려고 집을 알아보고 있다. 세 명의 친구 A, B, C가 있는데 이 친구들의 살고 있는 집으로부터 가장 먼 곳에 집을 구하려고 한다. 이때, 가장 먼 곳은 선택할 집에서 거리가 가장 가까운 친구의 집까지의 거리를 기준으로 거리가 가장 먼 곳을 의미한다. 예를 들어, X 위치에 있는 집에서 친구 A, B, C의 집까지의 .. 2021. 12. 15.

백준 1277 발전소 설치 Kotlin (다익스트라) 문제 출처 : https://www.acmicpc.net/problem/1277 1277번: 발전소 설치 첫 줄에는 발전소의 수 N(1 ≤ N ≤ 1,000)과 현재 남아있는 전선의 수 W(1≤ W ≤ 10,000)가 주어진다. 두 번째 줄에는 제한 길이 M(0.0 < M < 200,000.0)가 주어진다. 다음 N개의 줄에는 1번 발전소부터 N번 발 www.acmicpc.net 문제 엄청난 벼락을 맞아 많은 전선들이 끊어져 현재 전력 공급이 중단된 상태이다. 가장 심각한 문제는 1번 발전소에서 N번 발전소로 가는 중간의 전선이 끊어진 것이기에 일단 이 두 발전소를 다시 연결하는게 현재 해결해야할 첫 번째 과제이다. 발전소는 1번부터 N번까지 번호로 매겨져 2차원 격자 좌표 위에 있다. 그리고 몇몇 전선.. 2021. 12. 15.

백준 22255 호석사우로스 c++ (다익스트라) 문제 출처 : https://www.acmicpc.net/problem/22255 22255번: 호석사우루스 (1, 1) -> (2, 1) -> (2, 2) -> (2, 3) -> (3, 3) -> (3, 4) -> (4, 4) -> (5, 4) -> (5, 5) 8번 만에 갈 수 있고 이게 최소이다. www.acmicpc.net 문제 음머... 미련한 소인 호석사우루스는 융통성 따위 일절 가지지 않는다. 자신의 철칙에 맞게 우직하게 미궁을 탈출하려고 한다. 미궁은 N행 M열의 격자로 이루어져 있고 각 칸마다 입장하는 순간 받는 충격량이 있다. 같은 방을 여러 번 들어가면, 들어갈 때마다 같은 충격량을 받게 된다. 당연히 똑똑한 소라면 최소의 충격을 받으면서 미궁을 탈출하던가, 애초에 미궁에 안 빠지도록.. 2021. 11. 1.

백준 22870 산책 (large) Kotlin (다익스트라) 문제 출처 : https://www.acmicpc.net/problem/22870 22870번: 산책 (large) 첫 번째 줄에는 정점의 개수 $N$과 두 정점 사이를 잇는 도로의 개수 $M$이 공백으로 구분되어 주어진다. 두 번째 줄부터 $M + 1$ 번째 줄까지 정점 $A$, $B$와 정점 $A$에서 정점 $B$로 가는 거리 $C$가 www.acmicpc.net 문제 코로나로 인하여 확찐자가 되버려 오늘부터 산책을 하려고 한다. 산책할 경로를 정하려고 한다. 현재 있는 곳 S에서 출발하여 S와 다른 곳인 E를 찍고 다시 S로 돌아오는 경로로 만들려고 한다. 산책을 할 때 이미 갔던 정점을 또 가기 싫어 E에서 S로 올 때 S에서 E로 간 정점을 제외한 다른 정점으로 이동하려고 한다. 또한 산책 거리.. 2021. 9. 15.

이전 1 2 3 다음

티스토리툴바