최단거리 알고리즘이란그래프 상에서 두 정점 사이의 최단 경로를 찾는 알고리즘을 의미한다. 최단 경로 알고리즘은 지도 앱에서 최적의 경로를 찾거나, 네트워크 라우팅에서 가장 효율적인 데이터 전송 경로를 결정하는 등 다양한 분야에서 사용된다.- 그래프의 특정 노드에서 다른 노드까지 가장 짧은 경로를 찾는 방법을 제공한다. 1. Dijkstra 알고리즘한 노드에서 다른 모든 노드까지의 최단 경로를 구하는 알고리즘이다.가중치가 모두 양수일 때 사용 가능한 알고리즘이다.특정 시작점 → 모든 정점까지의 최단 경로를 구한다.그리드 기반으로 방문하지 않은 정점 중 최단 거리 정점을 계속해서 업데이트한다. ex) 노드 0을 기준으로 모든 정점 탐색하기1. 노드 0 까지 최단 거리 구하기0???? 2. 노드 3 까지 최단..
문제 M개의 우주 리스트가 주어졌을 때, 위 조건이 만족하는 경우 균등한 우주라고 판단한다. 균등한 우주의 쌍을 구하기 위해서, 균등한 우주의 개수를 K라 했을 때 조합을 통해 KC2로 쌍의 개수를 전부 구해야 한다. 위 조건을 성립하는지 확인하기 위해서 주어진 우주의 리스트들의 크기에 따른 순서를 관리하여, 다른 우주와 비교하여 균등한지 확인할 수 있다. 예를 들어Space 1 : 1 3 2Space 2 : 12 50 31 위 인 경우에 아래와 같이 표현할 수 있다.SortedSpace 1 : 1 3 2SortedSpace 2 : 1 3 2 i ~ j가 같은 규칙을 가지기 때문에 균등한 우주라 판단할 수 있다. 코드Correct codeimport sysinput = sys.stdin.readlinef..
문제회원 점수가 낮아야 회장 선거에 나갈 수 있다.각 회원의 점수는 "건너 건너서 다른 회원을 알수록" 점수의 크기가 높아진다.총 인원의 제한은 50명이므로, 최대 회원 점수는 50으로 생각할 수 있다. 코드from collections import dequen = int(input())arr = [list() for _ in range(n + 1)]while True: u, v = map(int, input().split()) if u == -1 and v == -1: break arr[u].append(v) arr[v].append(u)def bfs(pos): visited = [-1] * (n + 1) visited[pos] = 0 que = deq..
문제: 섬 연결하기 (그리디)해당 문제에서는 최소한의 비용으로 모든 섬을 연결해야 합니다.즉, 가장 적은 비용을 통해서 섬을 연결하는 것이 중요합니다.해당 문제를 MST 트리의 크루스칼 알고리즘을 사용하여 풀 수 있습니다.union-find 자료구조를 통해 두 노드가 연결되었는지 확인하고, 연결이 되지 않았다면, union() 처리합니다. 풀이 코드def solution(n, costs): costs.sort(key = lambda x: x[2]) island = [i for i in range(n)] def find(x): if island[x] != x: island[x] = find(island[x]) return islan..
