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++ / 3055 / 탈출 ( 너비 우선 탐색 )

https://www.acmicpc.net/problem/3055문제 요약사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 합니다. 이 숲에는 고슴도치가 한 마리 살고 있습니다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 합니다.티떱숲의 지도는 R행 C열로 이루어져 있습니다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있습니다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있습니다.매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있습니다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장합니다..

• format_list_bulleted BAEKJOON/BFS
• · 2025. 4. 21.
• textsms

C++ / 21924 /도시 건설 ( 최소 스패닝 트리 )

https://www.acmicpc.net/problem/21924문제 요약채완이는 신도시에 건물 사이를 잇는 양방향 도로를 만들려는 공사 계획을 세웠습니다.공사 계획을 검토하면서 비용이 생각보다 많이 드는 것을 확인했습니다.채완이는 공사하는 데 드는 비용을 아끼려고 합니다. 모든 건물이 도로를 통해 연결되도록 최소한의 도로를 만들려고 합니다. 위 그림에서 건물과 직선으로 표시된 도로, 해당 도로를 만들 때 드는 비용을 표시해놓은 지도입니다. 그림에 있는 도로를 다 설치할 때 드는 비용은 62입니다. 모든 건물을 연결하는 도로만 만드는 비용은 27로 절약하는 비용은 35입니다.채완이는 도로가 너무 많아 절약되는 금액을 계산하는 데 어려움을 겪고 있습니다.채완이를 대신해 얼마나 절약이 되는지 계산해야합니다..

• format_list_bulleted BAEKJOON/Minimum Spanning Tree
• · 2025. 4. 20.
• 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++ / 1922 / 네트워크 연결 ( 최소 스패닝 트리 )

https://www.acmicpc.net/problem/1922문제 요약 도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 합니다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 합니다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 합니다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미합니다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있습니다.)그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것입니다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비..

• format_list_bulleted 카테고리 없음
• · 2025. 4. 19.
• textsms