[ 알고리즘 ]

[백준] 1991. 트리 순회

📌문제 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 🎖️난이도 ✔️풀이 # sol1) dict & 재귀 n = int(input()) tree = {} for _ in range(n): item, left, right = input().split() tree[item] = (left, right) def preorder(item): print(item, end="") if tree[item][0] != ".": preorder(tree[item][0]) if tree[item][1] != "."..

[백준] 11404. 플로이드

📌문제 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 🎖️난이도 ✔️풀이 import sys input = sys.stdin.readline INF = int(1e9) n = int(input()) m = int(input()) graph = [[INF]*(n+1) for _ in range(n+1)] for i in range(1, n+1): graph[i][i] = 0 for _ in range(m): a, b, c = map(int, input().split()) graph[a][b] = min(c, g..

[백준] 11403. 경로 찾기

📌문제 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 🎖️난이도 ✔️풀이 # sol1) graph[i][i]도 못간다고 생각하고 무한으로 초기화 & 플로이드워셜로 최단거리 구하기 import sys input = sys.stdin.readline n = int(input()) INF = int(1e9) graph = [list(map(int, input().split())) for _ in range(n)] for i in range(n): for j in range(n): if graph[i][j] == 0: graph[i][j] = INF # 무한..

[백준] 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 ..