본문 바로가기

C++ STL, 알고리즘29

BFS, DFS 활용 문제 고찰 BFS 문제를 많이 접하다 보니, BFS 문제 유형에 대해서 생각해보게 되었다. 나는 문제를 일반화 시키는 것을 선호한다. 만능은 없지만 정답에 가까워지기 편하기 때문이다. 먼저 그래프를 사용해야할 것 같다는 감이 올 때, 그 감에 대해서 정의해보려고한다. 그래프 문제의 경우 1. 어디부터 어디까지 도달한다 2. 가는 길을 묻는다 3. 가는 길의 횟수를 묻는다 4. 영역을 나눈다 5. 전염? 된다 이런 식의 힌트를 문제에서 제공한다. 의심의 여지없이 그래프를 사용해야하고, 그래프 탐색 알고리즘을 사용해야하는 경우가 많다. 그래프 탐색 알고리즘 중 bfs를 사용해야할 때와 dfs를 사용해야할 때는 명확한데, 각각의 특성을 고려했을때 그 문제가 어느 알고리즘으로 해결해야할지 더욱 명확해진다. - 결국 bfs.. 2023. 11. 1.
c++ memset #include #include int arr[100]; int main(){ memset(arr, 0, sizeof(arr)); return 0; } 2023. 10. 24.
DFS 활용 Flood Fill 입력 5 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 0 1 1 3 3 3 3 3 3 3 3 3 1 1 3 3 3 1 0 1 1 1 1 0 0 0 0 0 0 0은 빈공간 1은 경계선 1,1은 색칠하고자 하는 위치 3은 칠할 숫자 struct Point{ int row, col; } int D[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} }; //상하좌우 int N, Board[MAX_N][MAX_N]; int main(){ cin >> N; for(int i =0; i Board[i][j]; } } int sr, sc, color; cin >> sr >> sc >> color; dfs(sr, sc, color); for(int i =0; i 2023. 10. 24.
BFS, DFS c++ - DFS란, 그래프 전체를 탐색하는 하나의 방법으로써, 하나의 가지(branch)를 모두 탐색한 이후에 다음 branch로 이동하는 방법이다. - 시작 노드에서 깊이가 커지는 방향으로 탐색을 진행하여 더 이상 방문할 인접 노드가 없는 경우 이전 노드로 돌아가서, 다시 깊이우선 탐색을 반복 - 시작점부터 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하고 넘어가는 방법 stack 또는 recursive(재귀 함수)로 구현. 1. 탐색 시작 노드를 스택에 삽입하고 방문처리 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 3. 2번의 과정을 수행할 수 없을 때까지 반복.. 2023. 10. 23.

티스토리툴바