Algorithm 💡/GraphTheory5 [백준 1647번] 도시 분할 계획 import sysinput = sys.stdin.readline# 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다.(양방향)# 각 길마다 길을 유지하는데 드는 유지비가 있다. # 임의의 두 집 사이에 경로가 항상 존재한다.# 마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다.# 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다.# 1. 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. # 2. 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다.# 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다.n, m = map(in.. 2024. 8. 1. [백준 1043번] 거짓말 https://www.acmicpc.net/problem/1043import sys from itertools import permutations from collections import deque input = sys.stdin.readline # 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다 # 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다 # 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다 # 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것 # 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다 # 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 .. 2024. 7. 10. [백준 1753번] 최단경로 - 다익스트라(Dijkstra Algorithm) 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net import sys import heapq input = sys.stdin.readline v, e = map(int,input().split()) INF = float("inf") graph = [[] for _ in range(v+1)] distance = [INF]*(v+1) start_node = int(input()) for _ in range(e): start, end, cost = map(int,input().s.. 2023. 10. 7. [백준 1916번] 최소비용 구하기 - 다익스트라(Dijkstra Algorithm) 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net import heapq import sys input = sys.stdin.readline n = int(input()) m = int(input()) INF = float("inf") graph = [[] for _ in range(n+1)] distance = [INF]*(n+1) for _ in range(m): start, end, cost = map(int,input().split()) graph[start].appen.. 2023. 10. 7. [백준 2668번] 숫자고르기 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net n = int(input()) graph = [[] for _ in range(n+1)] visited = [False]*(n+1) temp = [] answer = set() for i in range(1,n+1): graph[int(input())].append(i) def dfs(index): global answer for i in graph[index]: if visited[i]: answer |= set(temp) return visite.. 2023. 9. 16. 이전 1 다음
