문제 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이 유니온 파인드(Union-Find)를 활용한 문제다. 도시들의 연결 정보를 입력받아 합집합(Union) 연산을 수행하고 여행 계획에 포함되어 있는 도시들이 합집합인지 아닌지 판별하여 결과를 출력하면 된다. 코드 import java.util.* fun main() { val br = System.`in`.bufferedReader() val bw = System.out.bufferedWriter() var st : StringTokenizer val ..

문제 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 풀이 이 문제는 최소 신장 트리(Minimum Spanning Tree, MST)를 구하는 것으로 크루스칼 알고리즘을 사용한다. 신장 트리란 주어진 그래프에서 일부 간선을 선택하여 모든 노드를 연결하되 싸이클이 없는 트리이다. 여러 신장 트리들 중에서 간선의 가중치의 합이 최소인 것이 최소 신장 트리이다. 최소 신장 트리를 구하는 방법인 크루스칼 알고리즘은 최소 비용으로 모든 노드를 연결하기 위해 사용한다. 먼저 입력받은 그래프를 간선의 가중치를 기준으로 오름차순 정렬한다. 그 후, 가중치가 가장 낮은 간선부터 선택하여 유니온 파인드(Union-..

문제 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 풀이 유니온 파인드(Union-Find)를 활용한 문제다. 0으로 시작하는 입력은 두 집합을 합치는 합집합(Union) 연산을 수행하고, 1로 시작하는 입력은 두 원소가 같은 집합에 속하는지 확인한다. 유니온 파인드란 각 노드가 어떤 집합에 속하는지 판별하는 알고리즘이다. 이를 배열을 이용해 구현하는데 초기에는 배열의 각 요소에는 자신을 가리키도록 한다. Union 연산을 수행할 때는 배열의 값을 루트 노드의 값으로 변..

문제 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 풀이 BFS를 활용해 풀이하면 된다. 먼저 입력을 받고 치즈의 총량을 확인해준다. while문 반복을 통해 치즈가 없어 질 때까지 BFS 함수를 실행한다. 공기와 접촉되어 있는 치즈를 확인하기 위해 Queue에 공기를 담아가며 탐색하고 치즈를 만나면 체크해준다. BFS 탐색이 끝나면 체크되어 있는 치즈를 녹여주고 치즈의 총랑에서 빼준다. 모든 치즈가 녹으면 반복문을 종료하고 시간와 마지막으로 남은 치즈를 출력해준다. 코드 import java.util.* data class ..

문제 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 풀이 주여진 수열을 만들기 위해 스택의 push와 pop 과정을 통해 구현하는 문제이다. 먼저 예제 입력 1을 예시로 수열을 만드는 방법을 살펴보자. 4를 수열에 배치하기 위해서 스택에 1, 2, 3, 4를 넣어 {1, 2, 3, 4}인 상태를 만들고 4를 빼주면 된다. 수열은 [4]이 되고 스택은 {1, 2, 3}인 상태가 된다. 다음 3을 배치하기 위해 스택에서 3을 빼준..