반응형 알고리즘/트리19 [백준][Python] 1967번 트리의 지름 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 코드 import sys from collections import deque def dfs(a,l): queue = deque() queue.append((a,l)) while queue: a,l = queue.popleft() for na,nl in graph[a]: if distance[na] == -1: queue.append((na,nl)) distance[na] = distance[a]+nl return distance.index(.. 2022. 10. 11. [백준][Python] 14267번 회사 문화 1 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 코드 처음에는 칭찬을 받은 직원을 입력받을 때마다 트리를 순회해서 해당 직원의 부하 직원을 모두 찾아 값을 더해줬는데 시간 초과가 났다. import sys from collections import defaultdict def dfs(a,b): visit = [False]*(n+1) queue = [] queue.append(a) while queue: next = queue.pop() if visit[next]: continue visit[next] = Tr.. 2022. 9. 30. [백준][Python] 1240번 노드사이의 거리 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 코드 import sys from collections import defaultdict def find(a,b): queue = [] queue.append((a,0)) visit[a] = True while queue: next,len = queue.pop() if next == b: return len for i,l in dic[next]: if visit[i]: continue visit[i] = True queue.append((i,l+len)) n,m = map(int,input().split().. 2022. 9. 29. [백준][Python] 4803번 트리 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 코드 import sys from collections import defaultdict def check(j): ret = True queue = [j] while queue: a = queue.pop() if visit[a] == 1: # 사이클 ret = False visit[a] = 1 for k in dic[a]: if k == a: ret = False if visit[k] == 0: queue.append(k) return ret .. 2022. 9. 27. 이전 1 2 3 4 5 다음 반응형
