프림(Prim)의 MST 알고리즘 Prim 알고리즘은 특정 정점에서 시작해 신장 트리 집합을 단계적으로 확장해 나가는 방법입니다. 인접한 정점들 중에서 최저 간선으로 연결된 정점을 선택해 트리를 간선이 $n-1$개가 될 때까지 확장합니다. 최소 신장 트리 구하는 과정 예시로 한 그래프에서 Prim 알고리즘을 이용해 MST를 구해보도록 하겠습니다. 시작 정점은 0이라고 가정하겠습니다. 결론적으로 이 그래프의 최소 신장 트리는 마지막 사진에 색칠한 것과 같이 이루어짐을 알 수 있습니다. 코드로 구현하면 아래와 같습니다. typedef struct Graph { int n; // 정점의 개수 int weight[MAX_VERTICES][MAX_VERTICES]; } Graph; int selected[MAX_..

크루스칼(Kruskal)의 MST 알고리즘 Kruskal 알고리즘은 탐욕적인 방법(Greedy, 그리디)를 사용합니다. 그리디를 간략하게 설명하자면, 선택할 때마다 그 순간 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 방법입니다. 그리디는 근사적인 방법이기 때문에 항상 최적의 해답을 주지 않을 수도 있습니다. 하지만 Kruskal의 MST 알고리즘은 최적의 해답을 주는 것으로 증명되었기 때문에 이 방법으로 최적해(최단 경로)를 구할 수 있습니다. 알고리즘의 작동 방식은 다음과 같습니다. 그래프의 간선들을 가중치의 오름차순으로 정렬함 사이클을 형성하지 않는 간선을 찾아서 최소 신장 트리의 집합에 추가함 가장 낮은 가중치를 가진 간선을 먼저 선택함 만약 사이클을 형성하는 간선이 있다면 그..

Problem https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net Comment 2178번 문제의 입력이 기다란 string type임을 알 수 있습니다. 따라서 입력을 받은 후 배열에 넣어주기 위해 일일이 숫자로 바꿔주어야 합니다. 해당 코드는 BFS를 이용해서 풀었습니다. 접근하는 좌표를 방문했다고 체크한 다음, 현재 좌표('current point') 기준 상하좌우를 탐색해 갈 수 있다면 갈 수 있는 곳에 'current point'에 담겨있는 값의 1을 더해줍니다. 그렇게..

Problem https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net Comment 유기농 배추가 잘 담길 수 있도록 cin으로 좌표값을 받아서 cabbage 배열에 1로 저장해줍니다. 잘 저장된 cabbage 배열을 반복문으로 쭉 돌립니다. 0이 나오면 유기농 배추가 없는 것이니 그냥 넘어가고 1이 나오면 BFS를 해줍니다(사실 여기서 BFS를 하든 DFS를 하든 상관없습니다. 근데 전 BFS로 구현했습니다.) BFS 함수로 넘어가서, 1이 나온 그 자리를 기준..