For Programmer

https://www.acmicpc.net/problem/20955 20955번: 민서의 응급 수술 민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서 www.acmicpc.net 간단한 유니온 파인드 문제이다. 풀이 방식은 유니온 파인드 돌린 후 1. 만약 두 노드가 이미 연결되어 있다면 연산횟수 + 1 2. 모든 연산이 끝난 후 연결되지 않은 연결요소 집합이 몇개 존재하는지 set함수를 통해 체킹 import sys input = sys.stdin.readline def find(x): if x != parent[x]: parent[x] = find(parent[x])..

https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 보통의 유니온파인드 문제와 비슷하게 크게 어려운 문제는 아니다. 하지만 파이썬 사용자라면 1. 경로 압축 2. 유니온 바이 랭크 두가지 모두 최적화 해주어야 통과할 수 있다. import sys input = sys.stdin.readline # 1. 경로 압축 def find(x): if x != parent[x]: parent[x] = find(parent[x]) # 재귀를 돌며 해당 부..

해당 문제는 풀이가 많이 존재할 수 있으나 크게 생각나는 2가지 방법으로 구현했다. 1. 최대힙을 이용한 다익스트라 2. 중량을 내림차순 정렬 후 유니온 파인드 1. 최대힙을 이용한 다익스트라 import heapq import sys input = sys.stdin.readline def dijkstra(v1, v2): global ans q = [] heapq.heappush(q, (-(1

해당 문제는 BFS로 풀 수도 있고 모든 거리를 1로 두고 다익스트라를 돌려도 된다. 1. BFS 풀이 import sys from collections import deque input = sys.stdin.readline N, M, K, X = map(int, input().split()) # 도시의 개수, 도로의 개수, 거리 정보, 출발 도시 번호 graph = [[] for _ in range(N + 1)] for _ in range(M): a, b = map(int, input().split()) graph[a].append(b) ans = [] visited = [False] * (N + 1) def bfs(start): queue = deque([[start, 0]]) visited[star..

무지성 다익 돌리면 된다. 단, 다익을 구하기 위해 아주 큰값으로 초기화를 해줄텐데 다익스트라를 시작하기 전 0,0의 거리 비용을 초기에 입력받은 배열의 0,0에 있는 좌표의 값으로 시작하는 것이 아주 중요하다. import heapq import sys input = sys.stdin.readline def dijkstra(): q = [] heapq.heappush(q, (arr[0][0], 0, 0)) distance[0][0] = arr[0][0] while q: cost, r, c = heapq.heappop(q) if r == N - 1 and c == N - 1: return cost if cost > distance[r][c]: continue for i in range(4): nr = r..

간단한 DP문제이다. 약간 웰노운이라 쉽게 풀 수 있었다. 최대 2개만 고를 수 있기 때문에 실버이지 않나 생각해본다. 이 중반복문을 돌면서 한개 뽑았을때 2개뽑았을 때 나눠서 생각하면 쉽게 풀 수 있다. import sys sys.setrecursionlimit(10000) input = sys.stdin.readline N, M = map(int, input().split()) w_size = list(map(int, input().split())) dp = [1

가중치 있는 최단경로는 우선 다익스트라를 가장 먼저 떠올리면 된다. 그러나 해당 문제는 조금 생각을 해야 하는데 v1,v2 를 무조건 지나야 한다고 되어있다. 따라서 1 -> N 까지 가는데 v1,v2를 무조건 지나야 한다고 되어 있으므로 나올 수 있는 최단경로는 1 -> v1 -> v2 -> N 이거나 1 -> v2 -> v1 -> N 일 수밖에 없다. 따라서 두가지를 구한 후 그 중 가장 짧은 거리를 출력하면 된다. import heapq import sys def dijkstra(s, des, distance): q = [] distance[s] = 0 heapq.heappush(q, (0, s)) while q: cost, cur = heapq.heappop(q) if cur == des: ret..

단순한 다익스트라 문제이다. import heapq import sys input = sys.stdin.readline V, E = map(int, input().split()) K = int(input()) graph = [[] for _ in range(V + 1)] for i in range(E): a, b, cost = map(int, input().split()) graph[a].append((b, cost)) INF = 1e10 distance = [INF] * (V + 1) def dijkstra(s): q = [] distance[s] = 0 heapq.heappush(q, (0, s)) while q: cost, cur = heapq.heappop(q) if cost > distance[..