https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 이 문제는 0-1 bfs 문제이다. 0-1 bfs란?? 그래프의 간선에서 가중치가 0과 1로만 이루어진 bfs 문제를 말한다! 이 문제가 해당 케이스이다. -1, +1, *2 위치를 체크하는 것은 bfs와 다를 바 없으나, 가중치가 0인 간선이, 가중치가 1인 간선보다 더 앞에 삽입되어야 한다! 가중치가 0이라는 것은, 아무 cost가 없다는 것을 의미하기 때..
https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 분석 분류 그래프 이론, 다익스트라 문제 설명 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 입력 첫째 줄에 도시의 개수 ..
문제를 찾아보면 알겠지만 N개의 마을에 사는 N명의 학생들이 특정한 한 집에 모여 파티를 하고, 다시 집으로 돌아가는데 드는 비용 중 최대 비용을 구하는 것이다. 다익스트라 코드는 기본적인 코드이며, 우선 특정한 한 집(코드에서는 x)에서 각각 학생들의 집까지 거리를 구하기 위해 start를 x로 하고 다익스트라를 통해 최소신장트리를 구한다. 그리고 배열 하나를 만들어서 x마을부터 각 학생들의 집(1,2,...,N)까지의 최소거리를 더한다. 다시 for문을 반복하여 각각의 학생들(i번째 학생들)에 대해 다익스트라를 실행 한 뒤, 특정한 집(변수 x)에 도달하기까지 걸리는 최소비용을 구해서 배열에 더해준다. 최소비용중 최대를 구해야하므로 변수 res를 하나 두어 최대를 뽑아낸다. res를 처음에 0으로 초..
