728x90 그래프탐색9 [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] 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] 5247. 연산 📌 문제 https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📌 문제 접근 방법 bfs를 활용해서 각 계산값에 접근하는 방식으로 풀었다. 최대 재귀 깊이를 넘어가길래 가지치기를 해줬는데, 첫 번째 코드처럼 append하고 not in으로 탐색하는 방식은 시간초과가 났다. 그래서 두 번째 코드처럼 처음부터 모든 숫자만큼 리스트를 만들어주고 숫자가 중복되지 않도록 이미 나온 숫자는 1로 바꿔줬다. 📌 코드 from collections import deque def find_M(N): queue = deque() queue.append((N, 0.. 2021. 10. 14. [BOJ/Python] 1240. 노드사이의 거리 📌 문제 https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 📌 문제 접근 방법 인접 행렬을 만들고 노드 간 연결이 된 곳에 거리를 저장! → 시간 초과 인접 리스트로 바꾸고 리스트에 연결된 노드번호와 거리를 함께 저장 후 bfs로 탐색 인접 행렬로 그래프 탐색을 하는 경우 시간 초과가 될 때가 종종 있어서 인접 리스트를 우선적으로 쓰는 것이 좋을 것 같다! 📌 코드 from collections import deque def distance(x, y): queue = deque() queue.. 2021. 10. 4. 이전 1 2 3 다음 728x90