개발하는 고라니

1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net [BFS * m회 + Kruskal (=Union-Find, Sort)] 어느정도 발상의 전환이 필요한 문제라고 생각된다. 'S'에서부터 'K'를 찾아가는 것이 아닌 각각의 'K'에서 또다른 'K'나 'S'를 찾아가는 방법으로 풀어보았다. 그러므로 m개의 'K'가 주어지면, 각각의 'K'의 위치에서 BFS를 수행하며 다른 'K'나 'S'를 만날 때 간선의 정보를 만들어 List에 담아주었다. 이 때 크루스칼 알고리즘을 수행하려면 출..

1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net [Union-Find] 입력은 인접 행렬 형태로 주어지지만, 크루스칼 알고리즘을 사용할 때 처럼 모든 간선의 정보를 하나의 리스트에 담았고, 이 리스트를 가지고 유니온 파인드를 하여 서로 연결된 그래프라면 연결시켰다. 그리고 입력으로 주어진 m개의 여행 도시 배열의 각 원소의 부모가 첫 번째 원소의 부모와 다르다면 이 여행 순서는 이루어질 수 없으므로 "NO"를 출력한다. # Code public class Main { static class Edge{ int ..