전체 글

푼 날짜 : 2024.11.14푼 문제 : [2211] / 네트워크 복구사용한 언어 : python알고리즘 : 다익스트라(dijkstra)  접근방식 :다익스트라를 사용하여 최소비용을 계산한다.최소비용을 계산하며 어디서 출발해서 어디로 연결되는지(연결되는 A, B)를 같이 저장했다.이후 해당 연결된 A, B를 출력했다. 아래와 같은 예제를 살펴보면,4 51 2 11 4 41 3 24 2 24 3 3 그래프는 아래와 같이 그려지며 최단 비용으로 연결하는 것은 노란색과 같다.  코드 :import sysimport heapqN, M = map(int, sys.stdin.readline().split())graph = [[] for _ in range(N+1)]for _ in range(M): A, B,..

푼 날짜 : 2024.11.14푼 문제 : [22865] / 가장 먼 곳사용한 언어 : python알고리즘 : 다익스트라(dijkstra)  접근방식 :가장 가까운 친구의 집까지의 거리를 기준으로 거리가 가장 먼 곳을 찾기 위해 각 친구마다의 거리표를 만들었다.이후 반복문으로 min값을 뽑아 그 값이 가장 커지는 집을 정답으로 출력한다.만약 가장 먼 곳이 여러 곳이라면 번호가 가장 작은 땅의 번호를 출력한다. 예제로 그림을 그려보면 다음과 같이 그래프가 그려진다.  A, B, C친구의 거리표는 다음과 같이 나타난다.  123456A(1)014245B(2)104335C(5)437602 따라서 3번 집일 때 가장 가까운 거리가 4로 다른 집보다 가장 멀기 때문에 답은 3이 된다.   코드 :import sy..

푼 날짜 : 2024.11.12푼 문제 : [1719] / 택배사용한 언어 : python알고리즘 : 다익스트라(dijkstra)  접근방식 :행렬로 계산하는 거라 처음에는 당황했지만 인덱스 계산만 잘하면 된다!인덱스 계산 외에는 일반적인 다익스트라와 동일하다. 대신 이전 위치를 함께 저장해야 하므로 나는 튜플로 저장했다. 스페셜 저지 문제이므로 예제 출력과 다르게 나와도 맞는 경우의 수라면 정답처리 된다.(이런 문구가 없어서 처음에 고민했지만 걱정말고 제출해도 된다!) [ 예제 출력 ]- 2 3 3 2 21 - 1 4 5 51 1 - 4 5 63 2 3 - 6 62 2 3 6 - 65 5 3 4 5 - [ 내가 제출한 코드의 출력 ]- 2 3 3 2 2 1 - 1 4 5 5 1 1 - 4 1 6 3 2..

푼 날짜 : 2024.11.12푼 문제 : [5972] / 택배 배송사용한 언어 : python알고리즘 : 다익스트라(dijkstra)  접근방식 :일반적인 다익스트라이다.특징은 양방향 간선이라는 것 !  코드 :import sysimport heapqN, M = map(int, sys.stdin.readline().split())graph = [[] for _ in range(N+1)]for _ in range(M): a, b, c = map(int, sys.stdin.readline().split()) graph[a].append((b, c)) graph[b].append((a, c))heap = [(1, 0)]dist = [float('INF') for _ in range(N+1)]..

푼 날짜 : 2024.11.12푼 문제 : [10282] / 해킹사용한 언어 : python알고리즘 : 다익스트라(dijkstra)  접근방식 :일반적인 다익스트라로 풀었다. 이 문제에서 주의해야할 것은 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. computer[b].append((a, s))=> 따라서 b가 감염되어야 a가 감염되므로 위와 같이 작성한다.  코드 :import sysimport heapqT = int(sys.stdin.readline())for _ in range(T): n, d, c = map(int, sys.stdin.readline().split()) computer = [[] for _ in ran..

푼 날짜 : 2024.11.11푼 문제 : [1238] / 파티사용한 언어 : python알고리즘 : 다익스트라(dijkstra)  접근 방식 :각 위치에서 X까지 걸리는 시간 + X에서 각 위치까지 걸리는 시간을 계산하여 가장 오래걸리는 시간을 출력하도록 했다.  코드 : import sysimport heapqN, M, X = map(int, sys.stdin.readline().split())graph = [[] for _ in range(N+1)]for _ in range(M): start, end, time = map(int, sys.stdin.readline().split()) graph[start].append((end, time))def dijkstra(start): ..

푼 날짜 : 2024.11.11푼 문제 : [11779] / 최소비용 구하기 2사용한 언어 : python알고리즘 : 다익스트라(dijkstra)  접근 방식 :사실 다익스트라로 가장 적은 비용을 들이는 것은 어렵지 않았다.이 문제의 포인트는 적은 비용을 들인 어떤 경로로 왔는가! 이다. 따라서 나는 경로에 (어디서 왔는지, 얼마에 왔는지) 를 함께 저장했다.이렇게 하면 도착점에서 이전 경로로 돌아오면서 경로 파악을 할 수 있다.  예를 들어 기본 예시로 계산을 해보면 5 8 1 2 2 1 3 3 1 4 1 1 5 10 2 4 2 3 4 1 3 5 1 4 5 3 1 5 dist 는 아래처럼 출력된다.[(-1, inf), (0, 0), (1, 2), (1, 3), (1, 1), (4, 4)]  따라서 도착..

푼 날짜 : 2024.11.11푼 문제 : [1504] / 특정한 최단 경로사용한 언어 : python알고리즘 : 다익스트라(dijkstra)  접근 방식 :주어진 두 정점을 반드시 거쳐야 하므로 1 -> v1 -> v2 -> N1 -> v2 -> v1 -> N이렇게 두 경로를 계산해서 작은 값으로 출력했다. 따라서 1 -> v1 -> v2 -> N를 구하려면 (1 -> v1) + (v1 -> v2) + (v2-> N) 이렇게 경로에 대한 값을 각각 구해서 더해주었다.   코드 : import sysimport heapqN, M = map(int, sys.stdin.readline().split())graph = [[] for _ in range(N+1)]for _ in range(M): a, b,..