Python/백준
1774_우주신과의 교감
https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 이전 문제와 비슷하게 풀 수 있다. 1. 각좌표 받기 2. 연결되어 있는부분 노드 받기 3. 각 노드들간 거리를 계산해놓는 배열 만들기 [ (1,2,거리), (1,3,거리),(1,4,거리).... (n-1,n,거리) ] 로 만들어야 한다. 이때 1번 부터 시작인걸 생각하고 만들어야 한다. 4. 배열을 거리순으로 오름차순 정렬 ( 가까운 순서대로 ) 5. 부모 배열 만들기..
4386_별자리만들기
https://www.acmicpc.net/status?user_id=supersfel&problem_id=4386&from_mine=1 채점 현황 www.acmicpc.net 이역시 유니온파인드를 활용한 크루스칼 알고리즘을 활용하여 해결하였다. 처음에 각 별들의 좌표를 받는데, 이를 활용해서 각 별간의 거리를 모두 저장해주었다. 각 별들에게 1번,2번 .... 이름을 붙여주고 1-2 간의 거리 1-3번간의 거리... 를 반복해서 n-1,n번과의 거리까지 구해준다. 그 후 거리순으로 배열을 정렬해준 후에, 부모가 같지 않으면 두 집합을 합쳐준다. import sys input = sys.stdin.readline n = int(input()) star=[] for _ in range(n): x,y = m..
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()) ..