Algorithm/Graph188 [파이썬] 프로그래머스 : 다단계 칫솔 판매 (레벨3) [파이썬] 프로그래머스 : 다단계 칫솔 판매 (레벨3)https://school.programmers.co.kr/learn/courses/30/lessons/77486풀이방향성 생각트리 형태DFS를 이용해서 각 판매마다 부모를 타고 올라가면서 수익 전달하기탈출 조건은 root거나 전달 수익이 없는 경우전체코드from collections import defaultdict as ddimport syssys.setrecursionlimit(10**6)def solution(enroll, referral, seller, amount): G = dd(str) # 부모 연결 for c,p in zip(enroll, referral): G[c] = p answer = dd(int) .. 2024. 5. 8. [파이썬] 백준 1613 : 역사 (골드3) [파이썬] 백준 1613 : 역사 (골드3)https://www.acmicpc.net/problem/1613풀이방향성 생각특정 거리를 묻는다기 보다는 순서를 묻는 문제.위상 정렬이나 유니온파인드 + BFS로 생각한 풀이들은 중복 계산이 많이 발생해서 패스플로이드와샬로 테이블을 업데이트 한 후, 간선 정보를 이용해서 출력한다.전체코드import sysinput = lambda : sys.stdin.readline().rstrip()N,K = map(int,input().split())# 간선 정보 업데이트V = [[0]*(N+1) for _ in range(N+1)]for _ in range(K): a,b = map(int,input().split()) V[a][b] = 1# 플로이드와샬. st.. 2024. 5. 5. [파이썬] 백준 6497 : 전력난 (골드4) [파이썬] 백준 6497 : 전력난 (골드4) https://www.acmicpc.net/problem/6497 풀이 방향성 생각 MST를 만들어서 필요없는 간선의 cost가 얼마인지 구하자. 전체코드 import sys input = lambda : sys.stdin.readline().rstrip() def find(a): if parent[a] != a: parent[a] = find(parent[a]) return parent[a] def union(a,b): parent[max(a,b)] = min(a,b) while True: # TEST CASE : 입력 -> 간선 N,K = map(int,input().split()) if (N,K) == (0,0): break # edges를 내림차순으로.. 2024. 4. 13. [파이썬] 프로그래머스 : 부대복귀 (레벨3) [파이썬] 프로그래머스 : 부대복귀 (레벨3) https://school.programmers.co.kr/learn/courses/30/lessons/132266?language=python3 풀이 방향성 생각 모든 부대원이 출발 지점에 도착하는지 체크 -> 도착지에서 BFS 돌려서 각 부대원까지 거리 체크 간선 가중치가 모두 1이므로 BFS로 간단하게 풀이 가능 전체코드 from collections import deque, defaultdict as dd def solution(n, roads, sources, destination): # 간선 정보 받아주고 graph = dd(list) for a,b in roads: graph[a].append(b) graph[b].append(a) # V에 걸린.. 2024. 4. 7. 이전 1 ··· 21 22 23 24 25 26 27 ··· 47 다음