백준
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의 단독트리가 있음을 알 수 있다. 두번째 예시는 위와 같고 하나의 트리로 된것을 알 수 있다. 트리 구조는 결국 사이클이 돌지 않아야한다. 즉, 한번 방문했던 노드를 다시 방문하면서 뻗어나가지 않아야 한다는 특징이 있다. 만..
5639_이진검색트리
https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 자 이번에는 이진검색트리이다. 이진검색트리는 루트 노드가 왼쪽노드보다는 무조건 크고, 오른쪽 노드보다는 무조건 작은 수가 들어있는 트리이다. 결국 전위탐색이던 중위탐색이던 후위탐색이던 다른 탐색으로 찾으려면 왼쪽노드와 오른쪽 노드가 갈라지는 경계점과 루트노드를 찾아야 한다. 전위탐색으로 시작을 했으므로 값을 담아둔 해당 리스트에서 가장 앞의 값이 루트노드일 것이고, 해당 노드의 값보다..