아 드디어 나를 엄청나게 괴롭히던 다리 만들기 문제를 풀었다. 이 문제는 조건이 복잡해서 최대한 단순하게 생각하는 게 좋은데, 너무 어렵게 생각해서 며칠을 못 풀었던 문제다. 입력 값은 아래와 같다. 10 1 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1 0 1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 이 문제에서 며칠을 막힌 이유는 육지의 끝부분마다 다른 섬까지 도착하는 모든 경우의 수를 구하면 시간 초과가 일어나지 않을까하는 걱정때문이었다. 하지..

DFS로 풀었을때는 쉽게 풀었는데 플로이드-와샬로 풀었을때는 많이 애먹은 문제로, 이전에 경로 찾기 문제와 유사한 유형이다. 입력 값은 아래와 같다. 7 6 1 2 2 3 1 5 5 2 5 6 4 7 플로이드-와샬로 풀었을때 상당히 애먹었다. 이전 경로 찾기 문제에서도 출발지 -> 목적지가 직접 연결되지 않더라도 출발지 -> 경유지 -> 목적지가 가능하다면 출발지 -> 목적지가 가능하다는 내용이 있었는데, 이전 문제의 경우에는 모든 위치에 대하여 이동이 가능한지에 대해 물어보다 보니 플로이드-와샬로 쉽게 풀 수 있었다. 그런데 이 문제는 출발지가 1로 정해져 있어서 오히려 생각하는데 더 많은 시간이 들었다. 코드는 아래와 같다. #include #define MAX 101 int Network[MAX][..

이번 문제는 BFS 알고리즘의 응용 문제로 최단 거리를 구하는 문제다. 여태까지 풀었던 최단 거리 문제와 달리 여러가지 상황이 있을 수 있는데 문제를 보며 확인해보자. 이 문제는 여러가지 입력 값이 필요하다. 많은 돌발 상황이 나오기 때문이다. 먼저 가장 일반적인 상황의 입력 값을 살펴보자. 6 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 이런 경우에는 인접 행렬에서 익은 토마토 (1) 를 검색해서 BFS로 최단 경로를 찾으면 된다. 6 4 0 -1 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 이 경우에는 모든 토마토가 익을 수 없으므로 -1을 출력해야 한다. 일단 BFS로 탐색 후 인접 행렬에 0이 있는지 체크하면 된다. ..

이번에는 경로 찾기 기본 문제에서 아주 약간 변형된 문제에 대해서 알아보자. 아주 간단한 문제지만 그놈의 고정 관념 때문에 푸는데 상당히 많은 시간이 소요되었다. 이 문제는 BFS, DFS, 플로이드-와샬 알고리즘으로 풀 수 있으며, 재귀 함수 연습(?)을 위해 DFS로 풀었다. 입력 값은 아래와 같다. 7 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 코드는 아래와 같다. #include #define MAX 101 int map[MAX][MAX]; int result[MAX][MAX]; int visited[MAX]; void DFS (int start, int limit)..

완전 탐색에는 순열, 부분 집합, 조합이 있으며, 이번 문제는 9개의 숫자중 7개의 숫자를 선택해서 모두 더한 값이 100이 되는 경우의 수를 찾는 문제다. 입력값은 아래와 같다. 20 7 23 19 10 15 25 8 13 이번 문제는 재귀 함수를 이용하여 모든 경우의 수를 찾는 기본 문제로, 순열을 이용하면 쉽게 풀 수 있다. 순열이란, n개의 아이템 중에서 r개를 선택하여 순서대로 나열하는 것으로 완전 탐색 기법에 해당한다. #include int finish = 0; int minimum[9]; void show (int number) { int total = 0; insertsort(); for (int i = 0; i < number; i++) { printf("%d\n", minimum[i]..

별것 아닌거 가지고 상당히 오랜시간 삽질했다. 이번 문제는 다익스트라 알고리즘 기본 문제이며, 입력 값에 신경을 써야 하는 문제다. 이 문제의 입력값은 아래와 같다. 5 8 1 2 2 1 3 3 1 4 1 1 5 10 2 4 2 3 4 1 3 5 1 4 5 3 1 5 코드를 보며 이번 문제에 대해 분석해보자. #include #define MAX 1001 #define INFI 999999999 // 출발지서 각 도시간 최소 비용 int D[MAX]; // 방문기록 int Visited[MAX]; int Map[MAX][MAX]; void Dijkstra (int maxV, int startV, int destV) { // 최소 거리를 INFI로 초기화 for (int i = 1; i w) { Map[s..

DFS 심화 문제로 쉽게 풀 수 있다. 테스트에 사용된 입력값은 아래와 같다. 2 10 8 17 0 0 1 0 1 1 4 2 4 3 4 5 2 4 3 4 7 4 8 4 9 4 7 5 8 5 9 5 7 6 8 6 9 6 10 10 1 5 5 워낙 쉬운 문제라 딱히 주의해야 할 점은 없다. 테스트 케이스가 있으므로 케이스마다 결과 값을 저장하는 변수를 0으로 초기화하고 맵을 초기화하면 된다. #include #define MAX 50 int Map[MAX][MAX]; void DFS(int x, int y, int maxX, int maxY) { // 방문 표시 Map[y][x] = 0; // 왼, 오, 위, 아 체크 int dirX[] = {-1, 1, 0, 0}; int dirY[] = {0, 0, -1..

이번 문제는 BFS를 응용한 길찾기 문제에 대해 알아보자. 보통 미로 찾기 문제를 풀 때 BFS를 사용하는 이유는 DFS의 경우 도착지에 도달하지 못하는 경우, 무한 루프에 빠지지만 BFS는 큐의 아이템이 모두 빠져나가면 루프를 종료하기 때문에 도착 여부를 체크 할 수 있기 때문이다. #include #define MAX 101 #define INFI 999999 int Map[MAX][MAX]; typedef struct Queue { int x; int y; int s; } Queue; Queue Q[INFI]; int front = -1, rear = -1; void DFS (int maxY, int maxX) { // 왼, 오, 위, 아 int directX[] = {-1, 1, 0, 0}; in..