tose33

https://www.acmicpc.net/problem/16202 16202번: MST 게임 첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있 www.acmicpc.net 크루스칼을 이용한 MST (최소 스패닝 트리)를 찾는 문제였다. 기본적으로 MST를 찾고 MST의 가중치의 합을 구하는데, MST를 찾은 후에 MST를 이루는 간선들중 가중치가 가장 작은 간선을 없애고 또다시 MST를 만들어야 한다. 따라서 kruskal 알고리즘으로 MST를 만들되, 만드는 중 가장 작은 간선을 기억하고, 다음번 k..

인접 리스트 기반의 무방향 그래프 구현 연결리스트는 구현된것 사용. (DLinkedList.h, DLinkedList.c) ALGraph.h /* * 인접 리스트 기반의 무방향 그래프 구현 */ #ifndef CHAP14_ALGRAPH_ALGRAPH_H #define CHAP14_ALGRAPH_ALGRAPH_H #include "DLinkedList.h" // 연결 리스트 사용 // 정점의 이름 상수화 enum {A, B, C, D, E, F, G, H, I, J}; typedef struct _val { int numV; int numE; List *adjList; } ALGraph; // 정점갯수 nv개의 그래프 생성 void GraphInit(ALGraph *pg, int nv); void Grap..

www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 다시 푼 문제, 이전 글: tose33.tistory.com/29 2178. 미로탐색 과 같지만 다른점은 익은 토마토가 여러개 있을수 있어, 처음에 큐에 1개 이상의 값이 들어간다. 처음에 입력 받을때, 익은 토마토라면 미리 큐에 다 넣어준다. for(int i = 0; i < H; i++) { for(int j = 0; j < W; j++) { if(tomato[i][j] == 1) { // ..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net 이전의 bfs를 이용하는 문제인 미로탐색과 거의 같지만 한 가지가 다르다고 볼 수 있다. 미로탐색에서는 출발점에서 시작해서 도착점까지의 탐색이다 즉 출발점이 하나다. 토마토 문제는 1로 표현된 익은 토마토의 갯수가 출발점의 갯수이다. 그래서 그냥 출발점을 큐에 넣은 미로탐색 문제와는 다르게 일단 처음에 저장된 배열에서 이미 익어있는 토마토의 갯수를 세고, 그 토마토를 큐에넣는다...