목록백준/Graph (31)
mojo's Blog
[백준 2637] 장난감 조립
문제 링크 => 2637번: 장난감 조립 (acmicpc.net) 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 위상정렬 기본문제이다. 이 문제를 접근하기 위해 2차원 배열 result[x][y]를 설정하였다. (x번 부품에 대한 y번 부품의 갯수) 1. inDegree[x] == 0 이 되는 x는 기본 부품이며 기본 부품의 수를 1로 초기화 하고 기본 부품을 저장하도록 하는 벡터를 설정하여 push_back 해준다. => result[x][x] = 1 (x번 부품에 대한 x번 부..
[백준 6543] 그래프의 싱크
문제 링크 => 6543번: 그래프의 싱크 (acmicpc.net) 6543번: 그래프의 싱크 각 테스트 케이스마다 한 줄에 걸쳐 bottom(G)의 모든 노드를 출력한다. 노드는 공백으로 구분해야 하며, 오름차순이어야 한다. 만약, bottom(G)가 공집합이면 빈 줄을 출력한다. www.acmicpc.net SCC를 활용한 문제이다. SCC에 대한 vector들의 정보들을 v1, v2, v3, ... ,vt 라고 하자. 이때 v1의 size값이 v1에 존재하는 정점들에 대해서 SCC로 묶인 정점들로만 이동 가능한지를 파악하면 끝이다. 자세한 설명을 위해 예제 입력 1을 살펴보도록 한다. ex) 1 => 3, 2 => 3, 3 => 1 으로 주어진 그래프에 대하여 SCC는 다음과 같이 묶인다. v1 :..
[백준 1761] 정점들의 거리
문제 링크 => 1761번: 정점들의 거리 (acmicpc.net) 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 www.acmicpc.net 정점과 정점사이의 거리를 구하는 문제이다. 이 문제 역시 LCA 문제인데 다음과 같은 그림을 통해 해당 수식을 이해하기 전에 간단하게 배열들에 대한 설명을 하자면 다음과 같다. parent[x][y] => x 노드의 2^y 의 부모 depth[x] => x 노드의 깊이, 보통 1을 0으로 잡는다. path[x] => 1부터 x까지 연결된 노드의 길이 그렇다면 두 노드를 LCA를 통해 어..
[백준 11438] LCA 2
문제 링크 => 11438번: LCA 2 (acmicpc.net) 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 트리를 이용한 최소 공통 조상을 찾는 문제이다. 이문제는 LCA 11437번: LCA (acmicpc.net) 이 문제와 다르게 N 값이 100,000으로 주어졌다. 따라서 1차원 배열로 해결할 경우 시간 초과가 발생한다. 따라서 부모배열을 1차원 배열이 아닌 2차원 배열로 변경하여 parent[x][y] 로 수정해준다. parent[x][y] => x의 노드에서 2^y 위에 존재하는 부모..
[백준 11437] LCA
문제 링크 => 11437번: LCA (acmicpc.net) 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 트리에서 최소 공통 조상을 구하는 문제이다. 아이디어는 1을 최상단 노드로 잡아서 각 노드들의 부모 노드, 깊이등을 설정한 후, 임의의 두 노드의 가장 가까운 공통 조상을 찾도록 하는 것이다. 부모 노드를 표현하기 위한 배열 parent[x] 와 깊이 배열 depth[x] 을 먼저 살펴보면 다음과 같다. parent[x] : x의 부모 노드 depth[x] : x의 깊이 (0, 1, 2, 3, ...
[백준 19535] ㄷㄷㄷㅈ
문제 링크 => 19535번: ㄷㄷㄷㅈ (acmicpc.net) 19535번: ㄷㄷㄷㅈ 첫 번째 줄에 주어진 트리가 D-트리라면 D, G-트리라면 G, DUDUDUNGA-트리라면 DUDUDUNGA를 출력한다. www.acmicpc.net 트리를 활용한 경우의 수를 구하는 문제이다. 일단 G-Tree 를 구하는건 굉장히 쉽다. 현재 노드에서 이어져 있는 노드가 3개 이상인 경우 즉, n(n>=3)개로 이어져 있는 경우 G-Tree의 갯수는 nC3 = (n)(n-1)(n-2) / 3! 개이다. 그래서 모든 G-Tree를 구할 때 모든 노드를 방문하면서 n>=3 인 경우 nC3을 더해주면 그만이다. 문제는 D-Tree 이다. parent 노드와 child 노드를 잡으면서 동시에 두 노드가 연결되어 있는것은 분..