전체 글
-
[백준] 1967번 트리의 지름 (파이썬)
1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 코드 import heapq import sys n = int(input()) li = [[] for _ in range(n+1)] for _ in range(n-1): a, b, weight = map(int, input().split(" ")) li[a].append([b,weight]) li[b].append([a,weight]) INF = sys.maxsize def dikstra(start): destination = [INF] * ..
-
[백준] 1167번 트리의 지름 (파이썬)
1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 코드 import heapq import sys v = int(input()) li = [[] for _ in range(v+1)] for _ in range(v): input_li = list(map(int, input().split(" "))) for i in range(1, len(input_li)-1,2): node = input_li[i] length = input_li[i+1] li[input_li[0]].append([node, le..
-
[백준] 11725번 트리의 부모 찾기 (파이썬)
11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 코드 from collections import deque n = int(input()) tree = list([] for _ in range(n+1)) check_li = list(False for _ in range(n+1)) for _ in range(n-1): x, y = map(int,input().split()) tree[x].append(y) tree[y].append(x) queue = deque([]) queue.append(1) answer = {} while queue: x = queue.popleft() ..
-
[백준] 3273번 두 수의 합 (파이썬)
3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 코드 n = int(input()) li = sorted(list(map(int, input().split(" ")))) x = int(input()) answer = 0 start = 0 end = n-1 while start < end: plus = li[start] + li[end] if plus == x: answer += 1 if plus < x: start += 1 else: end -= 1 pr..
-
[백준] 11404번 플로이드 (파이썬)
11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 코드 import sys n = int(input()) m = int(input()) inf = sys.maxsize destination = list([inf]*n for _ in range(n)) def floyd(): for k in range(n): for i in range(n): for j in range(n): if i != j and destination[i][j] > destination[i][k]+destination[k][j]: destinat..
-
[백준] 11657번 타임머신 (파이썬)
11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 코드 import sys inf = sys.maxsize n, m= map(int, input().split()) destination = [inf]*(n+1) tree = list([] for _ in range(n+1)) is_possible = True def bellman(start): global is_possible destination[start] = 0 for repeat in range(..
-
[백준] 1504번 특정한 최단 경로 (파이썬)
1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 코드 import heapq import sys n, e = map(int, input().split()) inf = sys.maxsize heap = [] tree = list([] for _ in range(n+1)) def dijkstra(start): destination = [inf] * (n + 1) destination[start] = 0 heapq.heappush(heap, [destination[sta..
-
[백준] 1753번 최단경로 (파이썬)
1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 코드 import heapq import sys inf = sys.maxsize V,E = map(int, input().split()) k = int(input()) tree = list([] for _ in range(V+1)) destination = [inf]*(V+1) heap = [] def dijkstra(start): destination[start] = 0 heapq.heappush(heap, [0,start..