분류 전체보기
1197_최소스패닝트리
https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 최소 스패닝 트리는 간선의 합이 가장 적은 트리이다. 이를 위해서는 아래와 같이 해결하면 된다. 먼저 가중치를 기준으로 해서 간선의 정보를 정렬한다. 만약 1 2 3 2 3 2 1 3 1 와같이 입력이 들어온다면 1 3 1 2 3 2 1 2 3 과 같이 가중치가 작은 순으로 정렬을 해준다. 그 이후, 간선들과 연결된 노드들이 같은 트리에 있는지 확인한..
9372_상근이의 여행
https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 트리 구조를 하나 만들고 그래프를 순회하면서 트리를 도록 순서를 짰다 t = int(input()) for _ in range(t): n,m = map(int,input().split()) graph = [ [] for __ in range(n+1) ] for __ in range(m): a,b = map(int,input().split()) graph[a]...
4195_친구네트워크 ...반례?
https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 유니온 알고리즘을 활용하면 풀 수 있다. 우선 입력케이스로는 문자열이 나왔는데 이를 해결하기 위해서 딕셔너리를 사용해야 편하다. 즉, 사람 이름이 들어온다면 이를 인덱스로 삼는 형태로 해야 문제를 편하게 쓸 수 있다. 또한 친구네트워크의 개수가 필요한데, 나는 문제를 풀때 parents 딕셔너리안에 { ['이름' , 크기] } 식으로 저장했는데 문제를 풀고 생각해보니 그냥 조상을 저장하..
1976_여행가자
https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 문제에서 중요한건 굳이 bfs나 dfs를 사용하여 탐색을 할 필요가 없다는 것이다. 여행계획에 속한다는 말은 결국 한 그래프 안에 여행경로에 들어있는 점들이 들어있는지 찾아보면 되는 것이기에 union과 find 연산을 통해서 부모를 등록시켜주고, 여행계획하는 점들의 부모를 찾아내면 쉽게 풀 수 있다. import sys input = sys.stdin.readline n=int(input()) ..
1717_집합의 표현
https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 유니온 파인드를 사용하면 어떠한 노드가 그래프에 속해있는지 알 수 있다. 부모를 찾는 find연산과 유니온 연산으로 나누어져 있다. 우선 parents배열을 하나 만들어서 자신의 루트노드를 저장하게 한다. 문제에서 합집합을 만든다는건 결국 두 노드를 이어주어 하나의 그래프로 만든다는 의미이다. 그래서 트리구조를 활용해서 가장 부모노드 하나를 잡게한다. 이 ..
4803_트리
https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 문제 이해가 살짝 어려웠던 문제이다. 먼저 문제 예시를 그림으로 보면서 이해해보자 처음 입력케이스는 위와같다. 1,2,3,4 로 이루어진 트리 하나와 5,6의 단독트리가 있음을 알 수 있다. 두번째 예시는 위와 같고 하나의 트리로 된것을 알 수 있다. 트리 구조는 결국 사이클이 돌지 않아야한다. 즉, 한번 방문했던 노드를 다시 방문하면서 뻗어나가지 않아야 한다는 특징이 있다. 만..