본문 바로가기
반응형

파이썬99

[BOJ][Python]1504 풀이 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net import heapq import sys ssr = sys.stdin.readline INF = 200000001 def dijkstra(start, end): h = [(0, start)] min_dist = [INF for _ in range(n+1)] min_dist[start] = 0 while h: cur_dist, cur_node = hea.. 2023. 8. 1.
[BOJ][Python]1753 풀이 https://www.acmicpc.net/problem/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 ssr = sys.stdin.readline INF = 3000001 def dijkstra(start): h = [(0, start)] dist[start] = 0 while h: cur_dist, cur_node = heapq.heappop(h) if cur_dist > dist[cur_node]: continue.. 2023. 8. 1.
[BOJ][Python]18352 풀이 https://www.acmicpc.net/problem/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 import heapq import sys ssr = sys.stdin.readline INF = 300001 def dijkstra(): while h: cur_dist, cur_node = heapq.heappop(h) if cur_dist > dist[cur_node]: continue for next_dist, nex.. 2023. 7. 31.
[BOJ][Python]1967 풀이 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net from collections import deque import sys ssr = sys.stdin.readline n = int(ssr()) adj_list = [[] for _ in range(n+1)] for _ in range(n-1): line = list(map(int, ssr().split())) adj_list[line[0]].append((line[1], li.. 2023. 7. 30.
[BOJ][Python]1167 풀이 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net from collections import deque import sys ssr = sys.stdin.readline n = int(ssr()) adj_list = [[] for _ in range(n+1)] for _ in range(n): line = list(map(int, ssr().split())) for i in range(1, len(line), 2): if line[.. 2023. 7. 30.
[BOJ][Python]20040 풀이 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net import sys ssr = sys.stdin.readline def find(node): if uf[node] == node: return node else: uf[node] = find(uf[node]) return uf[node] def union(node1, node2): root1 = find(node1) root2 = find(node2) if root1 != root2: if .. 2023. 7. 29.
[BOJ][Python]1976 풀이 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net import sys ssr = sys.stdin.readline def find(node): if uf[node] == node: return node else: uf[node] = find(uf[node]) return uf[node] def union(node1, node2): root1, root2 = find(node1), find(node2) if root1 != root2: if ran.. 2023. 7. 28.
[BOJ][Python]4195 풀이 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net from collections import defaultdict import sys ssr = sys.stdin.readline def find(name): if uf[name] == name: return name else: uf[name] = find(uf[name]) return uf[name] def union(name1, name2): root1 = find(name1) roo.. 2023. 7. 27.
[BOJ][Python]1717 풀이 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net import sys ssr = sys.stdin.readline sys.setrecursionlimit(1000000) def union(node1, node2): root1 = find(node1) root2 = find(node2) if root1 != root2: if rank[root1] < rank[root2]: uf[root1] = root2 eli.. 2023. 7. 26.
[BOJ][Python]1043 풀이 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net from collections import deque import sys ssr = sys.stdin.readline def check_truth(): while q: p = q.popleft() for party in parties: if p in party[1:]: for i in party[1:]: if visited[i] == False: q.append(i) visited[i] = True n, m.. 2023. 7. 26.
반응형

티스토리툴바