728x90 ALGORITHM/SW Expert Academy44 [SWEA/Python] 5251. 최소 이동 거리 📌 문제 https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📌 문제 접근 방법 다익스트라(dijkstra) 알고리즘을 활용한 풀이 (프림 알고리즘과 비슷) 방문하지 않은 지점 중에서 이동거리가 최소인 지점을 찾는다. 2의 지점과 인접한 지점 중에서 아직 방문하지 않은 지점에서 이동거리를 비교해서 갱신한다. 📌 코드 import sys sys.stdin = open('input.txt') def dijkstra(start): distance[start] = 0 # 노드의 개수만큼 반복 for _ in range(N+1): min_idx = -.. 2021. 10. 15. [SWEA/Python] 5250. 최소 비용 📌 문제 https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📌 문제 접근 방법 bfs를 활용해서 인접한 지역으로 이동한다. 이동한 지역이 이동 전 지역보다 높을 경우, 차이를 저장해준다. 이동할 지역에 이미 저장된 비용보다 현재의 경로로 이동할 때의 비용이 더 덜든 다면, 비용을 갱신해준다. (이 조건이 있기 때문에 따로 방문체크를 안해줘도 된다! 방문체크를 하면 오히려 최소 거리로만 이동하게 된다.) 📌 코드 from collections import deque import sys sys.stdin = open('input.txt') de.. 2021. 10. 15. [SWEA/Python] 5249. 최소 신장 트리 📌 문제 https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📌 문제 접근 방법 크루스칼 알고리즘을 사용해서 풀었다. 간선을 가중치를 기준으로 내림차순 정렬을 해준다. 노드1, 노드2의 조상 노드가 다르다면 사이클이 만들어지지 않으므로 연결해준다. 3번의 과정을 반복하며 가중치를 더해서 출력해준다. 📌 코드 import sys sys.stdin = open('input.txt') def find_set(x): if x != parents[x]: parents[x] = find_set(parents[x]) return parents[x] def.. 2021. 10. 14. [SWEA/Python] 5248. 그룹 나누기 📌 문제 https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📌 문제 접근 방법 하나의 조를 집합으로 생각하고 각 집합마다 집합을 대표하는 수를 parents에 저장한다. (초기값은 자기자신) 입력 값에 따라 union함수를 실행시켜서 집합을 합친다. 모든 조를 다 짠 후, 전체 원소에 대해 find_set 함수를 실행해서 대표 숫자를 업데이트 해준다. 대표 숫자를 set으로 만들어서 중복값을 없애주고 길이를 출력하면 완성된 조의 숫자가 된다. (parents에 0도 포함되므로 1은 빼준다.) 📌 코드 import sys sys.stdin =.. 2021. 10. 14. 이전 1 2 3 4 5 6 ··· 11 다음 728x90