Dev_Diary

https://www.acmicpc.net/problem/10423최소 스패닝 트리 응용 문제입니다.노드끼리 연결할 때 각 노드에 순환이 생길 때 뿐만 아니라 각 노드의 그룹에 발전기가 속해있는지 체크해주고 두 그룹에 모두 발전기가 속해있다면 연결하지 않으면 됩니다.import sysinput = sys.stdin.readline## Union-Find# Finddef Find(group_list, n): # 자신이 그룹의 대표가 아니면 if group_list[n] != n: # 재귀적으로 업데이트 group_list[n] = Find(group_list, group_list[n]) return group_list[n]# Uniondef Union(gro..

https://www.acmicpc.net/problem/4179BFS 로 그래프를 탐색하는 문제입니다.다만 불과 사람이 동시에 움직이는데, 같은 위치에 동시에 있으면 사람은 이동 불가이므로 불 먼저 이동시켜주면 되겠습니다.import sysfrom collections import dequeinput = sys.stdin.readlinedef solution(R, C, labyr): # 불 데크 fire_dq = deque() # 사람 데크 hum_dq = deque() # 사람 방문 목록 hum_visited = [[True for _ in range(C)] for __ in range(R)] # 미로 탐색하며 위치 체크 for i in range(R): ..

https://www.acmicpc.net/problem/7662우선순위 큐를 두 개 사용해서 풀 수 있는 문제입니다.최대힙, 최소힙 두 개를 사용해 풀 수 있는데, 문제는 이 두 힙을 동기화 시키는 것 입니다. 가장 작은 수를 최소힙을 통해 제거했다고 가정하겠습니다. 최대힙에서는 이 수를 제거한 사실이 자동으로 업데이트 되지 않습니다. 그렇다고 최대힙에서 해당 수를 찾아 제거하는 방식은 우선순위 큐를 사용하는 이점을 살릴 수 없습니다. 그렇기에 우리는 다른 방식을 찾아야 합니다. 일반적인 방법으로 쿼리의 순서를 기억해 삭제했는지 체크하는 방법이 있습니다.그래프를 탐색할 때 탐색여부를 체크하기 위해 visited 를 만드는 것 처럼 삭제한 쿼리를 기억해 최대힙 / 최소힙 에서 해당 데이터를 삭제 시 이미..

https://www.acmicpc.net/problem/14284기초 다익스트라 문제입니다.간선을 정리해 다익스트라 알고리즘을 통해 최단 거리를 찾아주면 됩니다.import sysimport heapqinput = sys.stdin.readlinedef solution(n, m, edges, s, t): # 그래프 graph = [[] for _ in range(n+1)] for a, b, c in edges: graph[a].append([b, c]) graph[b].append([a, c]) # 최소 가중치 리스트 min_weights = [float('inf') for _ in range(n+1)] # 큐 hq = [[0, s]] ..

https://www.acmicpc.net/problem/14621최소 스패닝 트리 문제입니다.Union 을 진행하기 전에 엣지의 양끝에 있는 노드가 다른 성별을 이루고 있는지만 추가적으로 확인하면 풀 수 있습니다.import sysinput = sys.stdin.readline## Union-Find# Uniondef Union(group_list, node1, node2): # 그룹 g1 = Find(group_list, node1) g2 = Find(group_list, node2) # 같은 그룹이면 if g1 == g2: # 변합하지 않음 return False, group_list # 다른 그룹이면 작은 그룹으로 병합 if g1 > ..

https://www.acmicpc.net/problem/1715먼저 합친 카드패를 연속해서 더하게 되는 방식이므로 작은 패부터 더해주는 것이 최적의 수가 되는 전형적인 그리디 알고리즘 문제입니다.다만 여러 패들 중에 더한 패를 들고 계속 더하는 것이 아닌 더한 패를 다시 패들 속에 섞고 그들 중 가장 작은 패 두개를 더하는 방식으로 여러 번 진행해야 합니다.즉 추가하고 뽑고를 반복해야 하니 효율적인 진행을 위해 우선순위큐를 사용하는 것이 합리적입니다.import sysimport heapqinput = sys.stdin.readlinedef solution(N, bundles): # 번들 리스트 힙으로 치환 heapq.heapify(bundles) # 카운트 cnt = 0 #..

https://www.acmicpc.net/problem/18405구현 문제같지만 사실 단순한 계산 문제입니다.n 초가 지난 뒤 전염될 수 있는 칸은 각 행 / 열의 위치값 차이의 합이 n 인 인덱스입니다.즉 주어진 X, Y 와 초기에 바이러스가 존재하는 칸들 중 어느 칸과 가장 가까운지 알면 무조건 해당 칸과 같은 바이러스로 감염됩니다.다만 S 초 동안은 S 칸 만큼만 바이러스가 이동할 수 있으므로 행 / 열의 위치값 차이의 합이 S 이상일 경우 바이러스가 도달할 수 없음을 주의해야 합니다.import sysinput = sys.stdin.readlinedef solution(N, K, informs, S, X, Y): # 바이러스 위치 탐색 v_idxs = [[] for _ in range..

https://www.acmicpc.net/problem/1759조합 문제입니다.문자를 정렬 후 조합시키면 조합된 문자열이 나오니 이들 중 조건에 맞는 것을 필터링하면 됩니다.import sysfrom itertools import combinationsinput = sys.stdin.readlinedef solution(L, C, chr): # 조합 for comb in combinations(chr, L): # 한 개의 모음과 두 개의 자음 m = 0 j = 0 for c in comb: if c in 'aeiou': m += 1 else: j +=..

https://www.acmicpc.net/problem/16398최소 스패닝 트리 문제입니다.두 행성을 잇는 간선을 정리해 크루스칼 알고리즘으로 풀었습니다. import sysinput = sys.stdin.readline# union-finddef Union(group_list, n1, n2): # 그룹 g1 = Find(group_list, n1) g2 = Find(group_list, n2) # 두 그룹이 같으면 if g1 == g2: # 병합하지 않음 return False, group_list # 다르면 그룹이 작은쪽으로 병합 if g1 > g2: group_list[g1] = g2 else: ..

https://www.acmicpc.net/problem/17412네트워크 플로우 기본 문제입니다.에드몬드 카프 알고리즘으로 해결했습니다.import sysfrom collections import dequeinput = sys.stdin.readlinedef solution(N, P, edges): # 네트워크 플로우 # 1, 2 가 싱크, 소스 # 그래프 graph = [[] for _ in range(N)] # 흐를 수 있는 유량 flowable = [[0 for _ in range(N)] for __ in range(N)] for n1, n2 in edges: # 그래프 graph[n1].append(n2) graph[n..