C++ Programming20 [BOJ] 2667. 단지번호맞추기 백준의 2667번 문제를 DFS를 사용하여 재귀로 풀어보았다. #include #include using namespace std; #define MAX_SIZE 25 int dx[] = { -1,0,1,0 }; int dy[] = { 0,1,0,-1 }; int n; int group_id; int groups[MAX_SIZE * MAX_SIZE]; bool visited[MAX_SIZE][MAX_SIZE]; int map[MAX_SIZE][MAX_SIZE]; void dfs_recursion(int x, int y) { visited[x][y] = true; groups[group_id]++; for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y.. 2020. 5. 12. [BOJ] 11403. 경로 찾기 가중치가 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램. 정점의 개수는 1에서 100 사이의 정수이고, 맨 첫 줄에 주어징다. 둘째줄부터 N개 줄에 그래프의 인접 행렬이 주어지고, i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다. 출력은 N개의 줄에 걸쳐서 문제의 정답을 인접행렬로 출력하는데, 정접 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력한다. #include #include using namespace std; int arr[100][100] = { 0, }; int visi.. 2020. 5. 7. [C++] 깊이 우선 탐색(DFS : Depth First Search) 이번 시간에는 깊이 우선 탐색에 대해 알아보도록 하겠다. 깊이 우선 탐색(DFS)는 탐색을 할 때 보다 깊은 것을 우선적으로 하여 탐색하는 알고리즘이다. 이러한 깊이 우선 탐색은 맹목적으로 각 노드를 탐색할 때 주로 사용된다. 이전에 배웠던 너비 우선 탐색에서는 큐를 사용하였고, 이번 깊이 우선 탐색에서는 스택을 사용한다. 컴퓨터는 항상 스택의 원리를 사용하기 때문에 사실 스택을 사용하지 않아도 된다. 맨 처음에 시작 노드(Start Node)를 스택에 넣어주고 시작 노드를 방문했음을 알리는 방문 표시를 한다. 그 다음에는 다음의 알고리즘을 반복한다. 1. 스택의 최상단 노드를 확인한다. 2. 최상단 노드에게 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접 노드.. 2020. 5. 7. [C++] 너비 우선 탐색(BFS : Breath First Search) 이번 시간에는 너비 우선 탐색에 대해 알아보도록 하겠다. 너비 우선 탐색(BFS)은 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘이다. '맹목적인 탐색'을 할 때 사용할 수 있는 탐색 기법으로, '최단 경로'를 찾아준다는 점에서 '최단 길이'를 보장해야할 때 많이 사용한다. 큐를 사용한다. 시작점에서부터 가까운 것부터 탐색을 하겠다는 것이다. 맨 처음에 시작 노드(Start Node)를 큐에 삽입하면서 시작한다. 시작 노드를 방문했다고 표시를 해놓고, 그 이후부터 다음의 알고리즘을 반복한다. 1. 큐에서 하나의 노드를 꺼낸다. 2. 해당 노드에 연결된 노드들 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입한다. stl queue를 사용해서 구현해본 코드이다. #include #.. 2020. 5. 7. 이전 1 2 3 4 5 다음