분류 전체보기

[백준] 1753. 최단경로

📌문제 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 🎖️난이도 ✔️풀이 # 다익스트라 & 인접리스트 => sigle source, 양수 간선 존재 import heapq import sys input = sys.stdin.readline # 안해주면 시간초과 INF = int(1e9) v, e = map(int, input().split()) start = int(input()) graph = {i : [] for i in range(1, v+1)} dist = [IN..

[백준] 18352. 특정 거리의 도시 찾기

📌문제 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 🎖️난이도 ✔️풀이 # bfs & 인접리스트 from collections import deque import sys input = sys.stdin.readline # 안해주면 시간초과 # 도시개수(n), 도로개수(m), 거리정보(k), 출발도시번호(x: single source) n, m, k, x = map(int, input().split()) graph = {i:[] for ..

[개념 정리] DFS, BFS

[220601][스터디준비] - DFS DFS와 BFS란? wise-soybean-8bd.notion.site

[개념 정리] 최단 경로 (Shortest Path) 알고리즘

[220711][스터디준비] - 최단경로 최단 경로(Shortest Path) 알고리즘이란? wise-soybean-8bd.notion.site

[프로그래머스] 여행경로

📌문제 https://programmers.co.kr/learn/courses/30/lessons/43164 🎖️난이도 Level 3 ✔️풀이 # sol1) dfs(재귀) from collections import defaultdict answer = [] # answer에 경로 누적, answer[-1]을 src로 재귀 graph = defaultdict(list) visited = defaultdict(list) n = 0 def dfs(src, tmp_route): print(tmp_route, dict(visited)) if len(tmp_route) == n+1: # tmp_route가 이제 최종 답! global answer answer = tmp_route return if answer: #..