Algorithm/Graph188 [파이썬] 백준 1240 : 노드 사이의 거리 (골드5) [파이썬] 백준 1240 : 노드 사이의 거리 (골드5)https://www.acmicpc.net/problem/1240풀이방향성 생각입력이 작아서 $N^2$로도 풀리는 기본 문제노드마다 BFS를 돌려서 거리를 구한다.큐에 노드와 거리를 같이 전달해서 V를 boolean으로 설정하거나, visit에 거리를 저장해서 이전 노드에서 불러온다.전체코드from collections import deque# node X에서 BFS를 돌려서 얻은 거리 리스트 반환def bfs(x: int) -> list: V = [-1]*(N+1) V[x] = 0 Q = deque([x]) while Q: x = Q.popleft() for nx,cost in G[x]: .. 2024. 11. 15. [파이썬] 백준 1595 : 북쪽나라의 도로 (골드4) [파이썬] 백준 1595 : 북쪽나라의 도로 (골드4)https://www.acmicpc.net/problem/1595풀이방향성 생각BFS를 통해서 한 점에서 가장 끝 점으로 간 후 BFS를 돌려준다.트리의 지름을 구하는 문제와 동일한 발상전체코드from collections import deque, defaultdict as ddimport sysinput = lambda: sys.stdin.readline().rstrip()graphs = dd(list)while True: try: a,b,c = map(int,input().split()) graphs[a].append((b,c)) graphs[b].append((a,c)) except: .. 2024. 10. 1. [파이썬] 백준 1368 : 물대기 (골드2) [파이썬] 백준 1368 : 물대기 (골드2)https://www.acmicpc.net/problem/1368문제[문제]선주는 자신이 운영하는 N개의 논에 물을 대려고 한다.물을 대는 방법은 두 가지가 있다.1. 하나는 직접 논에 우물을 파는 것이고 2. 다른 하나는 이미 물을 대고 있는 다른 논으로부터 물을 끌어오는 법이다.각각의 논에 대해 우물을 파는 비용과 논들 사이에 물을 끌어오는 비용들이 주어졌을 때, 최소의 비용으로 모든 논에 물을 대는 것이 문제이다.[입력]첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다.다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다.다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어온다.이는 i번.. 2024. 9. 21. [파이썬] 백준 1197 : 최소 스패닝 트리 (골드4) [파이썬] 백준 1197 : 최소 스패닝 트리 (골드4)https://www.acmicpc.net/problem/1197풀이방향성 생각유니온 파인드로 구현.시간 줄이고 싶으면 모든 노드가 연결되면 탈출하는 방식으로 풀이.루프 방지를 위해서 항상 번호가 작은 노드를 루트로 한다.이 문제의 경우에는 그냥 넘어가지만, 모든 노드가 어떻게 연결되었는지 확인을 해야하는 경우에는 각 노드마다 find(node)로 경로압축을 꼭 해주자.전체코드import syssys.setrecursionlimit(10**6) input = lambda : sys.stdin.readline().rstrip()V,E = map(int,input().split())G = [list(map(int,input().split())) for .. 2024. 9. 3. 이전 1 ··· 18 19 20 21 22 23 24 ··· 47 다음