728x90 ALGORITHM/SW Expert Academy44 [SWEA/Python] 1249. 보급로 📌 문제 https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📌 문제 접근 방법 다익스트라 알고리즘 사용 출발지에서 인접한 위치를 탐색하며 원래 저장된 비용보다 현재 경로로 온 비용이 적다면 비용을 갱신하고, 현재 위치를 큐에 넣는다. 큐가 빌 때까지 2를 반복 후, 도착지에 저장된 비용을 출력한다. 📌 코드 from collections import deque import sys sys.stdin = open('input.txt') def restore(i, j): queue = deque() queue.append((i, j)) dxy =.. 2021. 10. 19. [SWEA/Python] 7465. 창용 마을 무리의 개수 📌 문제 https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📌 문제 접근 방법 어제 풀었던 그룹 나누기와 똑같은 방식의 풀이! 이번엔 다른 코드 참고 안하고 직접 제대로 구현해봤다. 📌 코드 import sys sys.stdin = open('input.txt') def find_leader(p): if p != leader[p]: leader[p] = find_leader(leader[p]) return leader[p] def know(p1, p2): l1 = find_leader(p1) l2 = find_leader(p2) if ran.. 2021. 10. 15. [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. 이전 1 2 3 4 5 ··· 11 다음 728x90