joseph0528 코딩 블로그

깊이 우선 탐색(DFS) 란 그래프를 탐색하는 방법 중 하나이다. 그림 1을 예시로 들어보자. DFS는 이름 그대로 깊이를 우선으로 탐색하는 방법인데 탐색을 시작할 정점을 A라고 정해보자. A에서 시작했을 때, A와 연결되어 있는 정점은 B, C이다. 이때 DFS는 자신과 연결되어 있는 정점을 먼저 탐색한다. 일단 B부터 탐색해 보겠다. 여기서 초록색은 이미 탐색한 정점, 파란색은 현재 도달한 정점이다. 여기서 B는 D와 E 를 갈 수 있다. A 도 갈 수 있지만 이미 탐색을 했기 때문에 D 와 E 중 하나를 탐색해 준다. 이번엔 D에서 탐색할 수 있는 정점을 보면 H밖에 없다. 그러므로 H를 탐색해 준다. H에 도달했을 때, H에서 갈 수 있는 정점은 E다. 만약 이 그래프에 방향이 있다면, 방향에 따..

요약하면 그래프가 주어지고, Q개의 쿼리에서 X, Y 가 주어지면 X, Y에서 시작하는 스패닝 트리의 최솟값을 구하라는 문제이다. 기존 스패닝 트리와는 다르게 두 점 X, Y에서 스패닝 트리가 시작할 수 있는데 이는 즉, 한 그래프 안에서 스패닝 트리가 2개가 나올 수도 있다는 소리가 된다. 그럼 이를 어떻게 해결할 수 있을까? 그 방법은 스패닝 트리의 특징을 생각해보면 알 수 있다. 스패닝 트리는 N개의 점에 대해 N-1 개의 간선을 가진다. 또 문제에선 X,Y 에서 시작하는 최소 스패닝 트리를 요구하기 때문에 N-1 간선에서 최대 1개의 간선을 제거할 수 있다. 간선을 2개 이상 제거 할 경우, 어떠한 점을 연결할 수 없게 된다. 그러므로 최대 선 1개만 지울 수 있다, 음수 가중치가 없기 때문에 선..

이 문제는 여러 가지 풀이 방법이 있지만 이 글에선 유니온 파인드(줄여서 유파)를 이용한 풀이를 사용하겠다. 이 문제를 간단히 요약하면 사용할 수 있는 정점이 주어지면 한 정점에서 다른 정점으로 갈 수 있는 모든 경우의 수를 구하라는 문제이다. 이때 n개의 정점들이 이어져있다고 해보자. n개의 정점들은 자신을 제외한 모든 정점에게 갈수 있다고 할 때 이 그룹에서 나올 수 있는 경우의 수는 n*(n-1)/2 개가 된다. 이 글에선 이걸 이용할 것이다. 일단 처음에 한 정점을 기준으로 번호를 다시 부여해준다.(이 글에선 1번 정점을 기준으로 했다.) 번호를 부여할때 자신의 부모 노드의 번호를 같이 저장한 뒤 입력을 받을 때 새로 부여된 자신의 번호와 부모의 번호를 함께 저장한다. 그 뒤 자신에게 부여된 번호..

문제를 요약하면 기존 입력에 N-M+1 개의 가중치가 L 인 간선을 추가로 만들어 모든 점끼리 갈 수 있게 할 때 두 빌라봉을 오가는데 드는 비용 중 가장 큰 값이 가장 작도록 N-M+1 개의 간선을 만드는 것이다. 즉 그래프가 1개 이상이라는 것인데 이때 각 그래프에서 점 하나를 골랐을 때 그 점과 한 그래프의 나머지 점들끼리의 거리의 최댓값이 가장 작은 점을 고른 뒤 한 그래프를 한 점이라고 했을 때 점들을 연결했을 때 점들 간의 거리의 최댓값이 가장 작아야 되기 때문에 점이라고 정의한 그래프의 값 중 가장 큰 값을 중앙에 두고 중앙을 중심으로 다른 점들이 중앙 점과 연결을 할 때 가장 작은 값을 찾을 수 있다. 맨 처음 그래프 내에서 거리의 최댓값이 가장 작은 값을 고르는 방법은 이전에 설명했던 사..

solved.ac 티어 : 골드 3 https://www.acmicpc.net/problem/12784 12784번: 인하니카 공화국 인하니카 공화국은 1번~ N번까지 N개의 섬으로 이루어진 나라이다. 이 나라에서는 섬 간의 왕래가 매우 어려웠지만, 위대한 다리 설계자 ‘진’이 두 섬을 연결하는 다리를 최소한의 개수로 만들 www.acmicpc.net 이 문제의 풀이는 생각보다 간단하다. 1에서부터 시작해서 dfs으로 끝점(괴도 루팡이 있다는 곳)까지 탐색하면서 지나온 길의 가중 치중 가장 작은 값을 찾고 모아지는 부분에서 더해주면 된다. 문제에 있는 예시로 설명을 해보겠다 괴도 루팡이 있을 수 있는 곳은 3,4,6,7번 점이다. 1부터 3,4,6,7인곳으로 dfs으로 탐색하면 된다. 일단 3부터 시작하..

solved.ac 티어 : 골드 4 www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 이문제는 의외로 간단한데 어떤 노드에서 와 연결된 노드들 중에 재일 마지막 노드까지의 거리가 첫 번째로 큰 값과 두 번째로 큰 값의 합이 그 노드를 포함했을 때 가장 긴 길이이다. 이걸 dfs으로 탐색하면서 노드별로 가장 긴 길이 중에서도 가장 긴 길이를 출력하면 된다 . 예시로 봤을 때 4번 노드를 포함하는 최대 길이는 8이다. 4의 자식 노드를 포함하는..

solved.ac 티어 : 골드 3 www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 어느 한 위치를 선택했을 때 그 위치에서 최대로 갈 수 있는 개수를 저장하고 dfs를 돌면 된다. 최대 개수 구하는 방법은 한쪽으로 쭉 내려가고 더이상 내려갈 수 없을 때부터 +1씩 해주면 된다. import sys sys.setrecursionlimit(10**9) input=sys.stdin.readline a=int(input()) l=[list(map(int,..

solved.ac 티어 : 플래 5 www.acmicpc.net/problem/14574 14574번: 헤븐스 키친 남규는 요즘 군입대를 기다리며 하루 종일 유튜브를 본다. 남규가 가장 좋아하는 채널은 ‘Heaven`s kichen’이다. 이 프로그램에서는 N명의 요리사가 매일 둘씩 요리 대결을 펼치고, 승리한 요리사 www.acmicpc.net 모든 간선을 이어주고 가중치는 로 해준다. 그리고 스패닝 트리를 만들어 준다음에 사용한 간선들을 저장해서 트리를 만든 다음 dfs으로 탐색을 하면서 밑에부터 위로 가면서 출력해주면 된다. import sys sys.setrecursionlimit(10**9) m=int(input()) e=[] def find(a): if uf[a]

solved.ac 티어 : 골드 3 www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 이 문제는 각 섬들마다 다리를 이어서 모든 섬을 오갈 수 있게 하면서 다리의 길이가 최소가 되게 해야 된다. 이때 다리의 길이를 두 점의 가중치로 생각하면 최소 스패닝 트리가 된다. 이제 입력을 dfs으로 탐색해서 섬을 나누고 다리를 이은 다음 최소 스패닝 트리를 구해주면 된다. import sys sys.setrecursionlimit(10**9) a,..