Binary Search |
#include <iostream> using namespace std; int BinarySearch(int dataArr[], int size, int findData) { int low = 0, high = size - 1, mid; while (low <= high) { mid = (low + high) / 2; if (dataArr[mid] > findData) high = mid - 1; else if (dataArr[mid] < findData) low = mid + 1; else return mid; } return -1; } int main() { int dataArr[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,24 }; int length = sizeof(dataArr) / sizeof(dataArr[0]); int input, ret; while (true) { scanf("%d", &input); ret = BinarySearch(dataArr, length, input); if (ret != -1) printf("data is located in %d.\n", ret + 1); else printf("no man\n"); } return 0; } |
인접 행렬이란 정점의 인접 관계를 행렬을 통해 나타내는 것을 말합니다.
dfs |
#include <iostream> using namespace std; int n; int map[30][30], visit[30]; void DFS(int v) { int i; visit[v] = 1; for (i = 1; i <= n; i++) { if (map[v][i] == 1 && !visit[i]) { printf("%d -> %d\n", v, i); DFS(i); } } } int main() { int start; int v1, v2; scanf("%d %d", &n, &start); while (1) { scanf("%d %d", &v1, &v2); if (v1 == -1 && v2 == -1) break; map[v1][v2] = map[v2][v1] = 1; } DFS(start); return 0; } |
n: map 의 크기
map: 간선 정보
visit: 방문 했는지 확인
DFS 돌리면, 방문한 자리 체크하고, 맵이 1인지, 방문하지 않았는지 확인. 전체적인 것을 한번 해 하려하지 말고, 처음 단계만 생각하고 나머지 부분을 확인하면서 수정하는 것이 좋습니다.
main 에서는 start 와 간선 정보에 대해서 입력을 받습니다. 그리고 DFS에 어디서 부터 시작할 것인지를 넣어주면 됩니다. 끝.
최단 거리 |
#include <iostream> using namespace std; int n, min; int map[10][10]; void DFS(int x, int y, int l) { if (x == n - 1 && y == n - 1) { if (min > l) min = l; return; } map[y][x] = 0; if (y > 0 && map[y - 1][x] != 0) DFS(x, y - 1, l + 1); if (y < n - 1 && map[y + 1][x] != 0) DFS(x, y + 1, l + 1); if (x > 0 && map[y][x - 1] != 0) DFS(x - 1, y, l + 1); if (x < n - 1 && map[y][x + 1] != 0) DFS(x + 1, y, l + 1); map[y][x] = 1; } int main() { int i, j; scanf("%d", &n); min = n*n; for (i = 0; i < n; i++) for (j = 0; j < n; j++) scanf("%d", &map[i][j]); DFS(0, 0, 1); printf("%d\n", min); return 0; } |
n: map 의 크기
min: 최단 경로
map: 문제에서 주어진 맵 입력받기
l: 최단 경로에 대해 저장, 이것을 저장. 마지막에 도착했을 떄의 l값을 저장하고 있어야 합니다.
DFS 에서 끝나는 return 문 입력받기,
갈라지면, 한쪽으로 쭉쭉 가서 다 해결한 다음에 다시 원상복귀를 시켜 줍니다. 그러기 위해서 map[y][x]=1 입력받습니다.