one Book a Day

기본적인 union-find로 무리짓고 대푯값의 갯수를 세는 문제입니다. def find(x): if parents[x] == x: return x parents[x] = find(parents[x]) return parents[x] def union(x, y): x = find(x) y = find(y) if x > y: x, y = y, x parents[y] = x for test in range(1, int(input()) + 1): N, M = map(int, input().split()) parents = {i: i for i in range(1, N + 1)} for i in range(M): a, b = map(int, input().split()) if find(a) != find(b):..

가중치가 있는 단방향 그래프의 왕복 최단거리를 묻는 문제로 정방향, 역방향으로 다익스트라를 그려준 후 합치면 왕복 최단거리를 구할 수 있습니다. (역방향 다익스트라는 돌아오는 경로에 대한 역탐색이기 때문) from heapq import heappop, heappush def dijkstra(graph, start): dp_dists = {i: float('inf') for i in range(1, N + 1)} dp_dists[start] = 0 heap = [] heappush(heap, (0, start)) while heap: cur_dists, cur_node = heappop(heap) for next_node, next_dist in graph[cur_node]: dists = cur_dis..

가중치 간선이 존재하는 2차원 배열의 이동 간 최소 cost를 묻는 문제로 다익스트라를 이용해 풀 수 있습니다. from heapq import heappush, heappop def dijkstra(x, y): heap = [] dists[x][y] = 0 heappush(heap, (0, 0, 0)) while heap: cur_dist, x, y = heappop(heap) for dx, dy in delta: nx, ny = x + dx, y + dy if 0

조합으로 거리구하고 간선 heap으로 정렬 후 n-1개만큼 연결 from heapq import heappop, heappush def find(x): if parents[x] == x: return x parents[x] = find(parents[x]) return parents[x] def union(x, y): x = find(x) y = find(y) if x > y: x, y = y, x parents[y] = x for test in range(1, int(input()) + 1): N = int(input()) X = list(map(int, input().split())) Y = list(map(int, input().split())) parents = {i: i for i in rang..

로직이 완전 깔끔하지는 못하지만 시간 내에 통과하도록 최소한의 연산을 하도록 노력함. 기본적으로 재귀를 통해 폭탄을 한발씩 떨어뜨리는 함수, 폭탄이 블록과 만나면 연쇄 폭발을 일으키는 재귀함수 폭발 후 빈칸에 블록을 중력을 적용해 채우는 함수. 3가지 함수와 남은 블록을 카운팅해주는 함수 1개의 함수 총 4개의 함수로 구성했으며 중간에 블록이 모두 터졌을 경우 바로 종료하지는 못했으나 더이상 N을 파고들지 않아도 W를 0~ W-1까지 순회해서 continue로 넘어가게 만듦. 모두 터지지 않을 경우의 로직은 효율적으로 짰다고 생각함. def delete_block(board, x, y, cnt): board[x][y] = 0 if cnt > 1: for i in range(1, cnt): for dx, ..

조합을 dfs로 짜고, 조합에 속한 요소와 속하지 못한 요소간 차이를 비교. 삼성기출 스타트와 링크. 웰노운 def choose_parts(cur_node, cnt): global min_gap if cnt == N // 2: S1, S2 = 0, 0 for i in range(N - 1): for j in range(i + 1, N): if check[i] and check[j]: S1 += S[i][j] + S[j][i] elif not check[i] and not check[j]: S2 += S[i][j] + S[j][i] min_gap = min(min_gap, abs(S1 - S2)) for next_node in range(cur_node, N): if not check[next_node]:..

dfs 분기를 이용해 사각형을 그리도록 직선이동 시킴. 간만큼 돌아오도록 dx, dy를 이용해 통제. # 기본적으로 방향성 유지 이동, 간만큼 돌아오도록 dx, dy 변수가 늘어났다가 0으로 돌아오게끔 통제. def dfs(x, y, dx, dy, direction, cnt): global max_size nx, ny = x + delta[direction][0], y + delta[direction][1] # 속행 if 0

최소 이동거리 문제로 인접리스트가 주어져 다익스트라로 풀이했습니다. from heapq import heappush, heappop def dijkstra(start): heap = [] dists[start] = 0 heappush(heap, (0, start)) while heap: cur_dist, cur_node = heappop(heap) for next_node, next_dist in graph[cur_node]: dist = cur_dist + next_dist if dists[next_node] > dist: dists[next_node] = dist heappush(heap, (dist, next_node)) for test in range(1, int(input()) + 1): N, ..

가중치가 있는 2차원 배열의 최소거리를 구하는 문제로 다익스트라를 사용했씁니다. from heapq import heappush, heappop def dijkstra(x, y): heap = [] dists[x][y] = 0 heappush(heap, (0, 0, 0)) while heap: cur_dist, x, y = heappop(heap) for dx, dy in delta: nx, ny = x + dx, y + dy if 0

기본적인 MST 문제로 간선이 주어졌기 때문에 크루스칼 알고리즘을 사용해 풀이했습니다. from heapq import heappop, heappush def find(x): if parents[x] == x: return x parents[x] = find(parents[x]) return parents[x] def union(a, b): a = find(a) b = find(b) if a > b: a, b = b, a parents[b] = a for test in range(1, int(input()) + 1): V, E = map(int, input().split()) parents = {i: i for i in range(V + 1)} edges = [] for __ in range(E): a,..