빠르게 성장하는 개발자

1. 문제는 이쪽으로https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do 2. bfs처음에는 수업시간에 배운 다익스트라를 이용해서 풀이해 보려고 했지만,시간복잡도 때문인지 자꾸 시간초과가 나서 bfs를 변형한 방법으로 풀이하였다.from collections import deque di = [-1, 1, 0, 0] dj = [0, 0, -1, 1] def bfs(i, j): # s는 시작지점 q = deque() q.append((i,j)) money[i][j] = 0 # 시작지점의 가격 처리 while q: l = len(q) for _ in range(l): si, sj = q.popleft() for d in range(4): ..

1. 다익스트라 알고리즘이란 무엇인가?MST 다음에 배워서 MST와 비슷한가? 싶었지만 약간 다른 다익스트라!MST는 모든 정점을 잇는 간선이 하나씩 존재해서 모든 정점을 다 이었다면, 다익스트라는 시작정점에서 끝정점으로 가는 경로 중에 가중치가 제일 적은 값을 고르는 알고리즘이다!이 때 특징은 ‘유향’ 그래프, 즉 A → B로는 갈 수 있지만 반대로 B → A로는 가지 않는 ‘방향’ 이 주어지는 그래프라는 것이다. 2. 다익스트라 알고리즘 python 으로 구현하기1. V개의 노드를 방문할 때마다 V개의 인접 노드에 대해서 검사하는 방식→ Prim 알고리즘과 유사한 방식, 시간복잡도가 O(V^2)로 큰편이다.T = int(input()) for tc in range(1, T+1): N, E = map(..