영최의 개발켈로그

✅ 이문제 처음 접근할 때 친구-친구(2점) -> G[a][b]==G[b][c] ; O(n^3)...친구-친구-친구-친구-친구-친구(5점) -> G[a][b]==G[b][c]==G[c][d]==G[d][e]==G[e][f] ; O(n^6)이렇게 생각해서 뭐야 플로이드워셜로 풀면 시간 오류 뜨겠는데 생각해서 1) 다익스트라를 N번 돌려서 풀었는데 ,2) 플로이드워셜을 DP랑 같이 사용해서 풀 수도 있는 문제였다. ✅ 처음 다익스트라로 풀때 실수했던 부분:처음 시작점을 지나고 나서 distance[start][nv] = nddistance[nv][start] = nd -> 이부분까지 갱신을 해줬는데 그러면 안된다.왜냐면 Dijkstra의 알고리즘에서 거리는 특정 시작 노드에서 다른 노드까지 한 방향으로만 계..

✅ 두 사람이 친구이거나, A와 친구이고, B와 친구인 C가 존재해야 된다. => 바로 플로이드 워셜 점화식 떠올림✅ 플로이드 워셜에서 주의할 점 a!=b여야함 명심 N = int(input())G = [list(input()) for _ in range(N)]V = [[0]*N for _ in range(N)]for k in range(N): for a in range(N): for b in range(N): if a == b: continue if G[a][b]=="Y" or (G[a][k]=="Y" and G[k][b]=="Y"): V[a][b]=1answer = 0for row in V:..

1️⃣ 다익스트라✅ 언제 사용? 음의간선 없을때 한지점에서 특정지점까지 최단거리 구할 때 사용✅ 시간복잡도(개선된) :  O(elogv) (100만 정도) (경우에 따라 BFS로도 풀 수 있음; 인접리스트: O(e+v),인접행렬  O(v^2))✅ 원리 :1) 출발노드 선정 -> 2) 최단거리 테이블 ∞로 초기화 (출발노드는 0으로) -> 3) 방문하지 않은 노드 중 최단 거리가 짧은 노드 선택 (처음엔 출발노드, 최단 거리가 0이니까)-> 4) 해당 노드를 거쳐 다른 노드로 가는 비용 계산하여 최단 거리 테이블 갱신-> 3),4) 반복✅ 최적화: 힙 사용(거리 가장 짧은 노드), 방문처리 대신 테이블에 기록된 거리와 비교하여 큰 경우 PASS✅ 기본 코드:import heapq# sys.stdin.rea..

링크: https://www.acmicpc.net/problem/1261✅ 벽을 부순다 = 벽의 비용을 더했을때 최소비용이된다 => 다익스트라import heapqM,N = map(int,input().split())graph = [list(map(int,list(input()))) for _ in range(N)]INF = int(1e9)distance = [[INF]*M for _ in range(N)]dr = [-1,0,1,0]dc = [0,1,0,-1]def dijkstra(start_r,start_c): distance[start_r][start_c]=0 q=[] heapq.heappush(q,(0,(start_r,start_c))) while q: dist,(..

✅ 특정노드사이의 비용을 최소비용으로 잘못판단했다. => 이부분(start_v1[v2],start_v2[v1]) / 어느 지점을 특히 지나가야한다면 그사이에서도 다른 노드를 지날때가 더 최소일 수도 있다는걸 명심하자#수정 후path_1_v1_v2_N = start_1[v1]+start_v1[v2]+start_v2[N]path_1_v2_v1_N = start_1[v2]+start_v2[v1]+start_v1[N]#수정 전v1_v2_cost=INFfor (node, cost) in graph[v1]: if node==v2: v1_v2_cost=costpath_1_v1_v2_N = start_1[v1]+v1_v2_cost+start_v2[N]path_1_v2_v1_N = start_1[v2]..

✅ 이동시 -1 이 있으므로 최대 max(N,K)*2만큼의 배열이 필요하다 (입력이 5 17 일때 : 5->10->20->17)import heapqINF = int(1e9)N,K = map(int,input().split())distance = [INF]*(max(N,K)*2+1)def dijkstra(start): distance[start]=0 q=[] heapq.heappush(q,(0,start)) while q: dist, now = heapq.heappop(q) if distance[now]next_dist: distance[next_now]=next_dist heapq.heappush(q,(..