민규의 흔적

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

2024년 6월 18일문제 링크 : 프로그래머스 - 가장 먼 노드 문제 접근 1번 노드에서 가장 먼 노드의 개수를 구하는 문제다. 한 노드에서 다른 노드들까지의 거리(one to all)를 구하는 문제라고 판단되어 다익스트라 알고리즘을 활용해야겠다 생각하였다. 모든 간선의 길이를 1로 간주하고 1번 노드에서 각 노드까지의 거리를 모두 계산한 후, 가장 먼 거리의 노드 개수를 출력하였다. 전체 코드 from collections import dequedef solution(n, edge): answer = 0 INF = 50001 graph = [[] for _ in range(n + 1)] for e in edge: graph[e[0]].append(e[1]) ..

2024년 6월 7일문제 링크 : 백준 1504번 - 특정한 최단 경로  문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.입력첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) ..

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)를 구하는 알고리즘이라는 점이다. (플로이드-워셜 알고리즘에 대..