문제 링크 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 소스 코드 import sys sys.setrecursionlimit(10**6) def main(): n = int(input()) visited = [False] * (n+1) distance = [0] * (n+1) graph = [[] for _ in range(n+1)] for _ in range(n-1): parent, child, weight = map(..
전체 글
문제 링크 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 소스 코드 import sys sys.setrecursionlimit(10**6) def main(): v = int(input()) graph = [[] for _ in range(v+1)] visited = [False] * (v+1) distances = [0] * (v+1) for _ in range(v): # 그래프 입력 받기 temp = list(map(int..
문제 링크 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 소스 코드 import sys from heapq import heappush, heappop def main(): n = int(input()) m = int(input()) graph = [[] for _ in range(n+1)] distance = [10**9] * (n+1) # 최댓값으로 초기화 for _ in range(m): a, b, c ..
문제 링크 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 소스 코드 import heapq def main(): n,k = map(int,input().split()) limit = 10**5 + 1 # 최댓값 INF = 10**9 # 비용 초기화 arr = [INF] * (limit+1) arr[n] = 0 hq = [] heapq.heappush(hq, (0,n)) while hq: # 다익스트라 cost..
문제 링크 https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 소스 코드 def main(): n,m = map(int,input().split()) # 오름차순 정렬(중복 제거) nums = sorted(list(set(list(map(int,input().split()))))) answers= [] def dfs(arr): if len(arr) == m: # 길이가 m이면 종료 answers.append(arr[:]) return for i..
문제 링크 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 소스 코드 import sys def main(): n = int(input()) m = int(input()) INF = int(1e9) # 초깃값 graph = [[INF for _ in range(n+1)] for _ in range(n+1)] for a in range(1,n+1): for b in range(1,n+1): if a == b: # 자기 자신으로 갈 때는 0 gra..