남남이루의 고군분투 🌳

다익스트라가 사용되는 때알고리즘 접근법 중 다익스트라는 가중치가 있는 그래프에서 최소 비용 경로를 구할 때 주로 사용한다. 파이썬에서의 다익스트라는 큐에서 가장 최소값을 꺼내기 위해 내장 라이브러리인 heapq를 사용하면 됐었지만 기본 자바스크립트에서는 heap을 지원하지 않기 때문에 직접 구현해서 쓸 수 있다.다익스트라의 구현큐에서 가장 최소값을 꺼내기 위해 heap이 아닌 우선순위큐를 구현해서 할 수도 있지만, 두 방식은 시간 복잡도에 큰 차이가 있다.구체적인 구현 방식을 서술해보자면, 우선순위 큐(Priority Queue)는 요소의 추가(삽입, push) 혹은 제거(꺼내기, pop)때 마다 정렬을 새로 해줘야 한다. 자바스크립트의 내장 sort는 N*logN 의 비용이 들고, 제거할 때 조차 배열..

DFS 답은 맞는데, 시간 초과 뜸 import sys input = sys.stdin.readline n = int(input()) # g = [[0]*(n+1)] + [[0] + list(map(int, input().split())) for _ in range(n)] g = [list(map(int, input().split())) for _ in range(n)] dx = [0,1] dy = [1,0] visited = [[0]*len(range(n)) for _ in range(n)] def DFS(x,y): global ways global visited if x==n-1 and y==n-1: ways+=1 visited = [[0]*len(range(n)) for _ in range(n)] ..

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) BFS 코드의 프레임 특징 from collections import deque ... def BFS(v): q = deque() q.append(v) while q: p = q.popleft() print(p) from collections import deque import sys sys.stdin = open('C:\\tech\\backjoon\\graph\\input3.txt','r') input = sys.stdin.readline res = [] def DFS(node): visit1[node] = 1 line = graph[node] for i in range(1,n+1): if line[i] == 1 and visit1[i] == 0: i..