728x90 그래프64 [python] 백준 11266 단절점 https://www.acmicpc.net/problem/11266 문제 해결단절점이란?정점을 제거했을 때 그래프가 두 개 이상으로 나누어지는 정점, 즉 없으면 두개의 그래프로 나누어진다고 생각단순 사이클을 이루는 점이거나 직선 그래프를 잇는 점이 아닌 여러 노드들을 잇는 교차로 점들을 단절점이라 생각하면 된다.풀이는 이해가 쉽지만 바로 풀기는 쉽지 않은 문제... CODEimport sysinput = sys.stdin.readlinesys.setrecursionlimit(10**5)def dfs(node, is_root): visit_order[0] += 1 # visit 번호 visit_order[node] = visit_order[0] child_cnt = 0 # 최소 진입순.. 2024. 7. 6. [python] 백준 11438 LCA 2 https://www.acmicpc.net/problem/11438 문제 해결최소 공통 조상을 찾는 알고리즘을 LCA (Lowest common ancestor)이라 한다.트리 구조에서 level을 가지고 층의 차이를 좁힌 다음 하나씩 동시에 level을 올려 parent를 확인한 다음 동시에 같은 parent가 될 때 까지 학인하는 알고리즘 코드이다. CODE import sysinput = sys.stdin.readlinemax_depth = 10000log = 21n = int(input())graph = [[] for _ in range(n+1)]for _ in range(n-1): a, b = map(int, input().split()) graph[a].append(b) gra.. 2024. 6. 6. [python] 20188 등산 마니아 https://www.acmicpc.net/problem/20188 문제 해결트리와 DFS를 사용해야한다는 것은 쉽게 알 수 있지만 어떻게 활용할지 매우 어려운 문제https://youtu.be/AQzKDzQqIRE다음 동영상을 봐도 어렵다... CODEimport sysinput = sys.stdin.readlinefrom collections import deque, defaultdictsys.setrecursionlimit(10**8)def dfs(cur, parent): global ans for child in graph[cur]: if child != parent: dfs(child, cur) dp[cur] += dp[ch.. 2024. 5. 22. [python] 백준 1507 궁금한 민호 https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 문제 해결 플로이드-위셜 방법을 써야한다는 것은 쉽게 알 수 있었다. 하지만 어떻게 끊는 것을 구현할 지 생각이 나지 않았는데 check를 통해서 끊게 된다면 check[i][j]=0을 통해 이를 저장할 수 있었다. CODE import sys input = sys.stdin.readline def main(): result = 0 for k in range(n): for i in range(.. 2024. 4. 6. 이전 1 2 3 4 ··· 16 다음 728x90
