본문 바로가기
728x90

그래프64

[python] 백준 1647 도시 분할 계획 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 문제 해결 조금 고민하면 한 번 노드를 다 이은 후 가장 긴 길이를 빼면 되지 않을까? 싶은 생각을 할 수 있다. 하지만 이 때 가장 긴 길이가 짧아서 나눌 때 최소 길이가 되지 않을 수 있지 않나? 생각을 하게 되었다. 하지만 정렬(sort)를 이용하여 가장 유지비용이 짧은 두 노드부터 이어가며 모든 노드를 다 이은 다음 가장 나중에 이은 노드를 뺀다면 최소.. 2024. 3. 1.
[python] 백준 2887 행성 터널 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 문제 해결 최소 거리를 측정해야하는데 각 축에서 가장 차이가 작은 값으로 거리를 정의한다. 축을 분리해서 정렬 후 (오름차순) 거리차를 계산하는 것은 짐작할 수 있다. 그 후 점을 연결시키는데 이미 연결 되어있으면 넘어가고 아니면 점을 연결하고 비용을 추가해준다. 연결 되어있고 아니고를 유니온-파인드(Union-find)를 통해 계산한다. 이와 같은 방법을 크루스칼.. 2024. 2. 24.
[python] 백준 23258 밤편지 https://www.acmicpc.net/problem/23258 23258번: 밤편지 $C = 3$일 때, 1번 정점에서 4번 정점으로 가는 경로 중 3번 정점을 지나는 경로는 반딧불이 3번 정점에서 8방울의 이슬을 마시고 잠들어버리기 때문에 불가능하다. 따라서 가능한 경로는 2번 정점 www.acmicpc.net 문제 해결 DP의 전형적인 문제이다. 우선 $\sum_{i=1}^{i=C-1} 2^{i} k일 때에 DP[k][i][j]이면 지날 수 없다. 하지만 지날.. 2024. 2. 18.
[python] 백준 1939 중량제한 문제 해결 처음에 BFS를 이용해서 문제를 풀려했지만 메모리 초과가 났다. 그러면 que안에 적게 넣어서 통과하는지를 확인해야한다. 방법이 잘 안떠올라서 다른 풀이를 참고했고 이분 탐색을 이용해서 통과할 수 있는 최댓값이 나올때까지 계속 돌려보는 방법이 있었다. 처음에 최솟값 1 최댓값 1000000000을 잡은 후 mid = (low+high)//2를 잡고 mid가 통과하면 low를 한칸 올려주고 통과하지 못하면 high를 한칸 내려주며 계속 시도하는 방식이다. 이를 low 2024. 1. 29.
728x90