C++ / 11779 / 최소비용 구하기 2 ( 데이크스트라 )

https://www.acmicpc.net/problem/11779문제 요약 n(1≤n≤1,000)개의 도시가 있습니다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있습니다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 합니다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력해야합니다. 항상 시작점에서 도착점으로의 경로가 존재합니다. 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어집니다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어집니다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어집니다. 그리고 그 다..

• format_list_bulleted BAEKJOON/Dijkstra
• · 2025. 4. 22.
• textsms

C++ / 1261 / 알고스팟 ( 데이크스트라 )

https://www.acmicpc.net/problem/1261문제 요약알고스팟 운영진이 모두 미로에 갇혔습니다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없습니다.알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 합니다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방입니다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 입니다. 단, 미로의 밖으로 이동 할 수는 없습니다.벽은 평소에는 이동할 수 없지만, 알고스팟의 ..

• format_list_bulleted BAEKJOON/Dijkstra
• · 2025. 4. 19.
• textsms

C++ / 13913 / 숨바꼭질 4 ( 데이크스트라 )

https://www.acmicpc.net/problem/13913문제 요약수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있습니다. 수빈이는 걷거나 순간이동을 할 수 있습니다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 됩니다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 됩니다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성해야합니다.문제 풀이1. 출발점과 도착점을 입력받습니다.2. 데이크스트라 탐색을 위해 dist 배열을 초기화 합니다.3. 최단 거리 노드들을 출력하기 위해..

• format_list_bulleted BAEKJOON/Dijkstra
• · 2025. 4. 19.
• textsms

C++ / 1238 / 파티 ( 데이크스트라 )

https://www.acmicpc.net/problem/1238문제 요약N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있습니다.어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비합니다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 합니다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원합니다. 이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구해야합니다.문제 풀이이 문제는 가는거리와 오는거리가 ..

• format_list_bulleted BAEKJOON/Dijkstra
• · 2025. 4. 19.
• textsms

C++ / 4485 / 녹색 옷 입은 애가 젤다지? ( 데이크스트라 )

https://www.acmicpc.net/problem/4485문제 요약젤다의 전설 게임에서 화폐의 단위는 루피(rupee)입니다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 됩니다!젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. [0][0]번 칸이기도 합니다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 자꾸 "젤다의 전설에 나오는 녹색 애가 젤다지?"라고 물어봤기 때문이다. 링크가 녹색 옷을 입은 주인공이고 젤다는 그냥 잡혀있는 공주인데, 게임 타이틀에 젤다가 나와있다고 자꾸 사람들이 이렇게 착각하니까 정신병에 걸릴 위기에 놓인 것입니다.하여튼 젤다...아니 링크는 이 동..

• format_list_bulleted BAEKJOON/Dijkstra
• · 2025. 3. 27.
• textsms

C++ / 1735 / 최단경로 ( 데이크스트라 )

https://www.acmicpc.net/problem/1753문제 요약 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성해야합니다. 단, 모든 간선의 가중치는 10 이하의 자연수입니다. 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어집니다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정합니다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어집니다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어집니다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수입니다. ..

• format_list_bulleted BAEKJOON/Dijkstra
• · 2025. 3. 20.
• textsms