728x90 Algorithm98 [SWEA/Python] 1251. 하나로 📌 문제 https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📌 문제 접근 방법 Prim 알고리즘을 사용하였다. 임의의 섬을 하나 선택하고 방문체크한다. 아직 방문하지 않은 섬을 순회하면서 현재 섬과의 거리와 이미 dist에 저장된 거리를 비교해서 더 작은 값을 dist에 저장한다. 방문하지 않은 섬을 순회하면서 dist가 최소인 섬을 고르고 방문체크한다. 4번의 섬이 2번의 섬과 연결된 것이므로 4번의 섬에 저장된 dist를 E를 곱해서 pay에 더해준다. 모든 섬을 방문할 때까지 위의 과정 반복 📌 코드 import sys sys.stdi.. 2021. 10. 15. [SWEA/Python] 2814. 최장 경로 📌 문제 https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📌 문제 접근 방법 처음엔 스택을 이용해서 dfs를 실행해줬었는데, 방문체크를 해제할 수가 없어서 재귀로 바꾼후, 완전탐색을 해줬다. 재귀로 구현하면 목적지를 어떻게 설정하지?가 문제였는데, 그냥 함수가 실행될 때마다 경로에 속한 정점의 개수를 갱신해주면 된다. 📌 코드 import sys sys.stdin = open('input.txt') def dfs(v, cnt): global max_cnt max_cnt = max(max_cnt, cnt) for w in range(1, N.. 2021. 10. 15. [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. 이전 1 ··· 14 15 16 17 18 19 20 ··· 25 다음 728x90