민규의 흔적

2024년 9월 26일문제 링크 : 백준 5972번 - 택배 배송 문제 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다.농부 현서에게는 지도가 있습니다. N (1 다음 지도를 참고하세요. [2]--- / | \ /1 | \ 6 / | \ [1] 0| --[3] \ | / \2 4\ | /4 [6] \ | / /1 [4]-..

2024년 5월 28일문제 링크 : 백준 18352번 - 특정 거리의 도시 찾기  문제 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.  이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다.  2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.입력첫째 줄에 도시의 개..

2024년 5월 22일다익스트라( 데이크스트라, Dijkstra ) 다익스트라 알고리즘은 그래프의 한 정점에서 모든 정점까지의 최단 경로를 각각 구하는 알고리즘으로, 에츠허르 다익스트라가 고안한 알고리즘이다. 다이나믹 프로그래밍을 활용해 중복 연산을 방지하며 최단 경로를 구한다는 특징을 지니고 있다. 플로이드-워셜 알고리즘과는 다르게, 다익스트라 알고리즘은 그래프 내에 음의 가중치를 가진 간선이 존재한다면 사용할 수 없다. 추가로 둘의 차이점이라면 다익스트라 알고리즘은 하나의 노드로부터 최단 경로(one - to - all)를 구하는 알고리즘인 반면, 플로이드-워셜 알고리즘은 가능한 모든 노드쌍들에 대한 최단 경로(all - to - all)를 구하는 알고리즘이라는 점이다. (플로이드-워셜 알고리즘에 대..