dfs4

• 

  [c++] 백준 - 1520 내리막길 (DFS + DP) 1. 문제 2. 입출력 및 예제 3. 문제 해설 상하좌우가모두 탐색이 가능하다. 그리고 제약조건이 존재한다. 바로 현재 위치보다 낮은 수로만 이동할 수 있다는 점이다. 기본적으로는 dfs탐색을 해야할 거 같았다. 결국 자신의 네 방향 중 자신보다 낮은 수가 존재한다면 이동 횟수는 상관없이 이동할 수 있는 것이고 결국 오른쪽 맨 아래 칸에 도달할 수 있는 지에 대한 여부가 중요했기 때문이다. 따라서 나는 상태를 3가지로 나누었다. -1 : 아직 방문하지 않은 곳이다. 0 : 방문한 경우이다. 0보다 큰 수 : 현재 지점에서 목적지까지 도달 할 수 있는 경우의 수가 존재하는 곳이다. 처음에는 이 문제를 백트래킹으로 접근했는데 시간초과가 났다. 물론 4가지 방향 ^ (500 * 500)이 최악의 경우라 당연히.. c++/알고리즘 2023. 2. 14.

• 

  [C++] 백준- 1189 컴백홈 (완전탐색 + DFS) 1. 문제 2. 조건 여기에서 내가 고민했던 점은 이 문제는 기존의 최단거리만을 구하던 BFS문제들과는 다르다는 점이다. 이동하는 거리는 상관이 없고 그저 제약 조건이라고는 T로 표시된 곳은 지나가지 못한다. 또한 갔던 곳은 지나가지 못한다는 점이다. 따라서 출발점에서 도착점까지 이동할 수 있는 모든 경우의 수를 탐색하여 거리를 구하고 내가 원하는 거리에 해당하는 경로의 수를 출력해야하는 완전탐색 문제였다. 그래서 나는 재귀함수를 이용해서 이 문제를 해결하였다. 3. 풀이 #include #include #include using namespace std; int R, C; int K; char map[10][10]; int visited[10][10]; int dx[4] = { -1, 0, 1, 0 }.. c++/알고리즘 2022. 5. 1.

• 

  [c++] BFS, DFS(너비 우선 탐색. 깊이 우선 탐색) 1. 그래프에서 탐색 알고리즘 문제를 풀다보면 많은 그래프들을 마주하게 된다. 대표적인 예가 미로에서 최단거리를 찾는 문제나 연결되어 있는 컴포넌트를 찾는 문제에서이다. 우리는 이렇게 그려져있거나 가상의 그래프를 탐색해야하는데 컴퓨터는 일정한 알고리즘에 의해 이러한 그래프들을 탐색한다. 그 중 대표적인 예가 DFS(깊이 우선 탐색 Depth-First-Search)와 BFS(Breadth-First-Search 너비 우선 탐색)이다. 2. DFS (깊이 우선 탐색)이란? 그래프가 위와 같이 존재할 때 다음 분기로 넘어가기전 해당 분기를 완벽하게 탐색한 후 넘어가는 탐색 방식이다. 위의 그림을 보면 한 번 이동한 줄기의 마지막에 도착할 때까지 그 분기를 탐색한 후 다음 분기로 넘어가는 것을 확인할 수 있다.. c++/알고리즘 2022. 4. 27.

• 

  백준-2468 안전영역 1. 안전영역(DFS) 이 문제 또한 DFS를 활용하여 깊이 탐색을 하는 문제였다. 앞서 문제와 한 가지 다른점은 앞서 유기농 배추 문제는 모든 배열의 값이 0아니면 1이 들어가서 바로 dfs를 탐색할 수 있었던 반면에 이 문제에서는 각 배열마다 다른 높이가 존재해서 높이를 비교하면서 가야한다는 점이 있었다. 하지만 메모리 적으로 여유가 있어 나는 먼저 침수 높이d와 비교해 더 낮은 지대를 1의 값으로 갖는 비교 배열을 만들어준 후 앞선 유기농 배추 문제와 같이 dfs를 실행해주었다. dfs함수에서는 우선적으로 방문 배열을 1로 표시해주어야 하는 것이 중요하다는 것을 명심하자. 다음은 내가 문제를 푼 코드이다. #include #include #include using namespace std; int .. c++/알고리즘 2022. 3. 29.