스톤헤드 부수기

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 난이도 : 골드 4 가장 긴 지름을 만드는 노드 node1과 node2가 있다고 가정한다면, 임의의 노드 1개에서 가장 먼 노드는 node1이나 node2 일 것입니다. 여기서 긴 지름에 참여하는 노드 1개를 구하고 나머지 하나의 노드를 구하면 node1과 node2를 둘 다 구할 수 있습니다. 가장 먼 노드는 dfs로 구했습니다. https://www.acmicpc.net/p..

https://www.acmicpc.net/problem/1944 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 난이도 : 골드 2 문제가 복잡하지만 크루스칼 알고리즘으로 풀 수 있습니다. S, K(포인트라 하겠음) 상관없이 모든 포인트끼리의 거리를 구해 우선순위 큐에 넣으면 됩니다. BFS를 통해 각 포인트를 출발점으로 해서 도달 가능한 모든 포인트까지의 거리를 구합니다. 크루스칼 알고리즘을 돌리고 parent 값(find)은 모두 0이어야 합니다. 만약 0이 아니라면 어느 ..

난이도 : 골드 4 크루스칼 알고리즘을 이용하여 풀었습니다. 크루스칼 알고리즘은 모든 간선을 오름차순으로 정렬하여 가장 작은 값부터 골라 MST(Minimum Spanning Tree)를 구성합니다. 단, 이때 사이클이 생기는 간선은 추가할 수 없습니다. 간선을 오름차순 정렬하여 하나씩 뽑는 것은 우선순위 큐, 사이클 검사는 Union-Find를 이용했습니다. 2020/11/06 - [정보/CS] - Union-Find 유니온 파인드 Union-Find 유니온 파인드 2020/11/06 - [문제풀이/자바] - [백준 1976] 여행 가자 (자바) [백준 1976] 여행 가자 (자바) 난이도 : 골드 4 도시들을 연결하여 주어진 도시가 하나로 이어져 있는지 확인하는 문제입니다. 이러한 문제 jellyin..

난이도 : 골드 4 크루스칼 알고리즘을 이용하여 풀었습니다. 별의 거리는 Math.sqrt(Math.pow(star[i].x - star[j].x, 2) + Math.pow(star[i].y - star[j].y, 2))입니다. 모든 별의 거리를 우선순위 큐에 넣고 크루스칼 알고리즘을 돌렸습니다. 정답 출력은 round를 이용했습니다. 전역 변수 int parent[] = 그룹의 대표를 나타내는 배열 함수 void main 입력을 받고 star, pq를 세팅합니다. 크루스칼을 돌리고 정답을 출력할 때 round를 이용했습니다. 0.666666이라는 수를 둘째 자리까지 출력해야 할 때를 예로 들면 0.666666*100 = 66.6666 여기서 반올림하면 67 그리고 다시 100으로 나누면 0.67이 됩니..

난이도 : 골드 2 크루스칼 알고리즘을 이용하여 풀었습니다. 크루스칼 알고리즘을 이용하기 위해서는 간선의 정보가 필요합니다. 행성의 최대 개수는 10만 개가 들어옵니다. 행성 간의 모든 간선을 구하려면 대략 100,000^2의 시간 복잡도가 걸립니다. 시간초과를 예상할 수 있는 크기입니다. 굳이 모든 행성 간의 거리를 구할 필요는 없습니다. 현재 행성에서 가까운 행성간의 거리만 구하면 됩니다. 간선의 가중치는 x, y, z의 최소 값입니다. 즉, 어떤 행성의 최소 가중치의 간선은 x, y, z별로 정렬한 후 앞, 뒤의 값을 비교하여 구할 수 있습니다. 이해가 되지 않는다면 코드를 보며 이해하시길 바랍니다. 전역 변수 int n = 행성의 수 int parent[] = 그룹의 대표를 나타내는 배열 Plan..

난이도 : 골드 2 유니온 파인드 문제입니다. 하지만 입력은 숫자가 아닌 문자열이 주어집니다. map을 이용하여 각 이름(문자열)마다 숫자를 부여해줬습니다. 그리고 이 숫자를 기준으로 union-find를 했습니다. count는 초기 값을 모두 1로 갖습니다. n1, n2가 가지는 count 값을 union을 할 때 대표에게 값을 몰아줍니다. 그리고 이 값을 출력합니다. f번 다른 이름이 2개씩 들어올 수 있으므로 최대 배열 크기는 2*f로 했습니다. 전역 변수 int parent[] = 그룹의 대표를 나타내는 배열 int count[] = 친구의 수 함수 void main 입력을 받고 count와 parent 배열을 초기화해줍니다. f번 입력을 받으며 map에 이름이 없을 경우에 문자열 이름과 번호를 ..

2020/11/06 - [문제풀이/자바] - [백준 1976] 여행 가자 (자바) [백준 1976] 여행 가자 (자바) 난이도 : 골드 4 도시들을 연결하여 주어진 도시가 하나로 이어져 있는지 확인하는 문제입니다. 이러한 문제는 유니온 파인드(Union-Find)를 이용하여 풀 수 있습니다. 유니온은 도시들을 묶고 파인 jellyinghead.tistory.com 위에서 유니온 파인드에 대한 설명을 잠깐 했습니다. 하지만 제가 이 개념을 이해하고 왜 부모 값(대푯값)을 자꾸 건드리는지 이해하는데 많은 시간이 걸렸습니다. 아래 예시를 통해 이해를 하길 바랍니다. 위의 형태로 각 노드를 연결했고 밑은 그 출력문입니다. 초기값은 0~5였지만, union 후에 001111로 바뀐 것을 볼 수 있습니다. 이것은 ..

난이도 : 골드 4 도시들을 연결하여 주어진 도시가 하나로 이어져 있는지 확인하는 문제입니다. 이러한 문제는 유니온 파인드(Union-Find)를 이용하여 풀 수 있습니다. 유니온은 도시들을 묶고 파인드는 이러한 도시의 대표를 찾습니다. 그룹의 대표를 그 그룹에서 가장 작은 값으로 정했습니다. 대표는 그룹마다 통일성을 가진다면 어떤 값으로 해도 상관은 없습니다. 단, 이 대표를 통하여 그룹을 구분할 수 있어야 합니다. 예를 들면 [1, 2, 3, 4, 7, 8], [5, 6], [9]의 그룹은 각 그룹의 대표를 1, 5, 9로 설정합니다. 각 그룹의 대표를 저장하는 parent배열을 위와 같이 나타내 볼 수 있습니다. 최적화를 위해 그룹의 대표를 건드릴 때는 find를 이용합니다. parent 절대 xx..