분리집합

알고리즘 문제) BOJ 14621. 나만 안되는 연애  14621번: 나만 안되는 연애입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의www.acmicpc.net문제 요약아래 조건을 만족하는 경로의 총 길이 구하기남초 대학교와 여초대학교를 연결하는 도로로만 구성어떤 대학교에서든 모든 대학교로 이동 가능해야함최단 거리가 될 것시간 제한2초입력학교 수 N, 도로 수 M2 ≤ N ≤ 10001 ≤ M ≤ 10000각 학교가 남초 대학교면 M, 여초 대학교면 WM개의 줄에 u v d가 주어짐u학교와 v학교가 연결되어있으며, 거리가 d1 ≤..

알고리즘 문제) BOJ 14167. Moocast  14167번: MoocastFarmer John's N cows (1≤N≤1000) want to organize an emergency "moo-cast" system for broadcasting important messages among themselves. Instead of mooing at each-other over long distances, the cows decide to equip themselves with walkie-talkies, one forwww.acmicpc.net문제 요약농부 존의 N마리 소 (1 ≤ N ≤ 1000)은 각각의 (x, y)좌표에 위치해 있음비용 X 를 지불하면 거리 제곱 합이 X이하인 간선을 모두 연결..

알고리즘 문제) BOJ15559. 내 선물을 받아줘 15559번: 내 선물을 받아줘첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000, 1 www.acmicpc.net문제 요약N*M지도가 있다지도 각 칸에는 N,W,E,S가 적혀있다.N : (i-1,j)S : (i+1,j)W : (i,j-1)S : (i,j+1)해당 위치로 순간이동구사과는 (i,j)에 위치해있고, 계속 이동한다.위치에 관계없이 최소 몇 개의 칸위에 선물을 놓아야 항상 선물을 가져갈까?시간 제한2초입력N*M1≤N,M≤1,0001N개의 줄에 지도가 주어진다.지도를 벗어나는 경우는 없다.출력최소 몇 개의 칸에 선물을 놓아야 할 까?접근법피리부는 사나이랑 똑같은 문제(정리 글 접근법 참고)칸에 적힌 방향으..

알고리즘 문제) BOJ 16724. 피리 부는 사나이  16724번: 피리 부는 사나이첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주www.acmicpc.net문제 요약N*M 지도가 있고, 각 칸에 움직일 수 있는 방향이 적혀있음움직일 수 있는 방향U : 위쪽D : 아래쪽L : 왼쪽R : 오른쪽이때, 더 이상 움직일 수 없을 때 특정 지점에 SAFE ZONE을 설치하려고 함SAFE ZONE은 어느 구역에 있더라도 들어갈 수 있을 것이때 SAFE ZONE의 최소 개수 출력하기시간 제한1초입력지도 행 개수 N, 열 개수 M1 ≤ N ≤ 1..

알고리즘 문제) BOJ 16202. MST 게임 16202번: MST 게임첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있www.acmicpc.net문제 요약N개의 정점, M개의 양방향 간선으로 이루어진 단순 그래프 존재단순 그래프 : 자기자신으로 이어주는 간선X, 임의의 두 정점 사이 최대 1개 간선 존재MST 만족하는 조건간선 개수는 노드 개수-1임의 두 정점을 골랐을 때, 두 정점을 연결하는 경로를 구성할 수 있어야 함MST 게임그래프에서 간선을 하나씩 제거하면 MST 비용 구하기각 턴의 점수 = ..

알고리즘 문제) BOJ 4195. 친구 네트워크 4195번: 친구 네트워크첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진www.acmicpc.net문제 요약친구 관계가 주어 질때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하기친구 네트워크 → 같은 연결요소시간 제한3초입력테스트 케이스 개수각 테스트 케이스별로친구 관계수 FF개의 줄에 친구 관계가 주어짐(아이디)알파벳 대문자 또는 소문자(길이 20이하 문자열)출력친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명 있는지 출력접근법일단 입력이 문자열로 주어진다. → Map에 로 기록해둘 것..

알고리즘 문제) BOJ 1414. 불우이웃돕기 1414번: 불우이웃돕기첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선www.acmicpc.net문제 요약N개의 방에 각각 컴퓨터 한 개씩 존재컴퓨터는 랜선으로 연결되어 있음이때, N개의 컴퓨터를 모두 서로 연결되게 하고 싶다.그리고 나머지 랜선은 기부를 하려고 할 때, 기부할 수 있는 랜선의 길이의 최댓값 출력시간 제한2초입력컴퓨터 개수 N50보다 작거나 같은 자연수랜선의 길이가 주어짐i번째 줄의 j번째 문자가 0인 경우 컴퓨터 i와 j를 연결하는 랜선이 없음을 의미알파벳은 랜선의 길이a~z : 1~26A~Z..

알고리즘 문제) BOJ 14950. 정복자 14950번: 정복자서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재www.acmicpc.net문제 요약N개의 도시(1~N)와 M개의 도로(양방향)로 구성모든 도시 쌍에는 도로로 이어져 있음각 도로는 비용이 존재모든 도시를 정복하려고 함처음 점거 중인 도시는 1번 도시만약 B도시를 점거하고 싶다면, B와 연결된 도시 중 최소 하나 정복해야 함만약 A선택하면 B정복과정에서 A와 B를 연결하는 도로 비용도 소모한 번 도시가 정복 되면 모든 도로의 비용이 t만큼 증가이미 정복한 도시는 또 정복 X모든 도시 정복하는 데 드는 최소..

알고리즘 문제) BOJ 20303. 할로윈의 양아치 20303번: 할로윈의 양아치첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$,www.acmicpc.net문제 요약한 아이의 사탕을 뺏으면 그 아이 친구들의 사탕도 모조리 뺏을 수 있음K명 미만으로 뺏어야 함이때 최대로 뺏을 수 있는 사탕의 양은?시간 제한1초입력N M KN : 거리에 있는 아이들 수 (1 ≤ N ≤ 3만)M : 아이들 친구 관계 수 (0 ≤ M ≤ 10만)K : 미만으로 뺏어야할 아이 수 (1≤ K ≤ min(N, 30..

알고리즘 문제) BOJ 20040. 사이클 게임 링크 : https://www.acmicpc.net/problem/20040문제 요약0부터 n-1의 번호가 부여된 고유한 점들이 N개 주어지며, 매 차례마다두 점을 선택 해 선분을 이음이 때 사이클이 만들어지는 순간을 찾아서 해당 몇 번째 차례에서 처음으로 만들어졌는지 출력(없다면 0 출력)시간 제한1초입력첫 번째 줄에는 점의 개수를 나타내는 정수 3 ≤ n ≤ 500,000 과 진행된 차례의 수를 나타내는 정수 3 ≤ m ≤ 1,000,000 이 주어진다이어지는 m 개의 입력 줄에는 각각 i번째 차례에 해당 플레이어가 선택한 두 점의 번호가 주어진다출력사이클이 처음으로 만들어진 차례의 번호를 양의 정수로 출력m 번의 차례를 모두 처리한 이후에도 종료되지 ..