Algorithm/Graph188 [파이썬] 백준 11404 : 플로이드 (골드4) [파이썬] 백준 11404 : 플로이드 (골드4)https://www.acmicpc.net/problem/11404풀이방향성 생각a에서 b로가는 간선정보가 다수 들어올 수 있으니, 최소값을 그래프에 저장해준다.이후 플로이드워셜로 풀이전체코드import sysinput = lambda : sys.stdin.readline().rstrip()N = int(input())G = [[1e9]*(N+1) for _ in range(N+1)]for _ in range(int(input())): a,b,cost = map(int,input().split()) G[a][b] = min(G[a][b],cost)for i in range(1,N+1): G[i][i] = 0for k in range(1,N+.. 2024. 8. 1. [파이썬] 백준 1967 : 트리의 지름 (골드4) [파이썬] 백준 1967 : 트리의 지름 (골드4)https://www.acmicpc.net/problem/1967풀이방향성 생각모르면 노드마다 $N^2$로 돌리겠지만, BFS 두 번으로 해결이 가능하다.루트노드인 1번 노드에서 BFS를 돌리고, 가장 먼 지점에서 다시 한 번 BFS전체코드from collections import dequeimport sysinput = lambda : sys.stdin.readline().rstrip()N = int(input())G = [[] for _ in range(N+1)]for _ in range(N-1): a,b,cost = map(int,input().split()) G[a].append((b,cost)) G[b].append((a,cost.. 2024. 8. 1. [파이썬] 백준 14938 : 서강그라운드 (골드 4) [파이썬] 백준 14938 : 서강그라운드 (골드 4)https://www.acmicpc.net/problem/14938풀이방향성 생각다익스트라 기본문제입력에서 노드 번호가 1번부터라서 이 부분만 맞춰주면 된다.다익에서 최소비용을 기록하고 그 비용이 주어진 범위 내에 있으면 아이템을 획득한다.모든 노드에 대해 다익을 돌리고 최대 아이템을 출력한다.전체코드import heapq as hqimport sysinput = lambda : sys.stdin.readline().rstrip()N,M,R = map(int,input().split())items = [0] + list(map(int,input().split()))G = [[] for _ in range(N+1)]for _ in range(R): .. 2024. 7. 31. [파이썬] 백준 29792 : 규칙적인 보스돌이 (골드5) [파이썬] 백준 29792 : 규칙적인 보스돌이 (골드5)https://www.acmicpc.net/problem/29792풀이방향성 생각딱 보면, 캐릭(가방)으로 최대의 값을 구하는 문제원래는 냅색으로 캐릭당 2중 for문, 총 3중 for문으로 풀 수 있다.$2^{13}K$라서 각 캐릭터로 BFS를 돌려도 충분히 가능한 문제전체코드from collections import dequeN,C,B = map(int,input().split())dmgs = [int(input()) for _ in range(N)]dmgs.sort(reverse=True)boss = [tuple(map(int,input().split())) for _ in range(B)]def bfs(dmg): V = [0]*(B+1.. 2024. 6. 22. 이전 1 ··· 19 20 21 22 23 24 25 ··· 47 다음